Czumaj, Artur and Sohler, Christian (2007) On testable properties in bounded degree graphs. In: 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Los Angeles, 07-09 Jan 2007. Published in: Proceeding SODA '07 Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms pp. 494-501. ISBN 9780898716245.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

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 (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Journal or Publication Title:	Proceeding SODA '07 Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
Publisher:	SIAM
ISBN:	9780898716245
Official Date:	2007
Dates:	Date Event 2007 Published
Number of Pages:	8
Page Range:	pp. 494-501
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Conference Paper Type:	Paper
Title of Event:	18th ACM-SIAM Symposium on Discrete Algorithms
Type of Event:	Other
Location of Event:	New Orleans, Los Angeles
Date(s) of Event:	07-09 Jan 2007
Related URLs:	http://www.siam.org/meetings/da07/

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item