Czumaj, Artur and Sohler, Christian (2007) On Testable Properties in Bounded Degree Graphs. In: 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, JAN 07-09, 2007. Published in: PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS pp. 494-501.

Full text not available from this repository.

Abstract

We study graph properties which are testable for bounded degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and graphs that are far from every graph having that property. It is believed that almost all, even very simple graph properties require a large complexity to be tested for arbitrary (bounded degree) graphs. Therefore in this paper we focus our attention on testing graph properties for special classes of graphs. We call a graph family non-expanding if every graph in this family is not a weak expander (its expansion is O(1/log(2) n), where n is the graph size). A graph family is hereditary if it is closed under vertex removal. Similarly, a graph property is hereditary if it is closed under vertex removal. Next, we call a graph property H to be testable for a graph family F if for every graph G epsilon F, in time independent of the size of G we can distinguish between the case when G satisfies property H and when it is far from every graph satisfying property II. In this paper we prove that In the bounded degree graph model, any hereditary property is testable if the input graph belongs to a hereditary and non-expanding family of graphs. As an application, our result implies that, for example, any hereditary property (e.g., k-colorability, H-freeness, etc.) is testable in the bounded degree graph model for planar graphs, graphs with bounded genus, interval graphs, etc. No such results have been known before and prior to our work, in the bounded degree graph model very few graph properties have been known to be testable for any graph classes.

Item Type:	Conference Item (UNSPECIFIED)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics
Divisions:	Faculty of Science > Computer Science
Journal or Publication Title:	PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS
Publisher:	SIAM
ISBN:	978-0-898716-24-5
Date:	2007
Number of Pages:	8
Page Range:	pp. 494-501
Publication Status:	Published
Title of Event:	18th ACM-SIAM Symposium on Discrete Algorithms
Location of Event:	New Orleans, LA
Date(s) of Event:	JAN 07-09, 2007
URI:	http://wrap.warwick.ac.uk/id/eprint/5149

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item