The Library
Testing hereditary properties of nonexpanding boundeddegree graphs
Tools
Czumaj, Artur, Shapira, Asaf and Sohler, Christian. (2009) Testing hereditary properties of nonexpanding boundeddegree graphs. SIAM Journal on Computing, Volume 38 (Number 6). pp. 24992510. ISSN 00975397

PDF
WRAP_Czumaj,_GetPDFServlet3.pdf  Published Version  Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (375Kb)  Preview 
Official URL: http://dx.doi.org/10.1137/070681831
Abstract
We study graph properties that are testable for boundeddegree 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 well known that in the boundeddegree graph model (where two graphs are considered "far" if they differ in epsilon n edges for a positive constant epsilon), many graph properties cannot be tested even with a constant or even with a polylogarithmic number of queries. Therefore in this paper we focus our attention on testing graph properties for special classes of graphs. Specifically, we show that every hereditary graph property is testable with a constant number of queries provided that every sufficiently large induced subgraph of the input graph has poor expansion. This result implies that, for example, any hereditary property (e.g., kcolorability, Hfreeness, etc.) is testable in the boundeddegree graph model for planar graphs, graphs with bounded genus, interval graphs, etc. No such results have been known before, and prior to our work, very few graph properties have been known to be testable with a constant number of queries for general graph classes in the boundeddegree graph model.
Item Type:  Journal Article  

Subjects:  Q Science > QA Mathematics  
Divisions:  Faculty of Science > Computer Science  
Library of Congress Subject Headings (LCSH):  Graph theory  
Journal or Publication Title:  SIAM Journal on Computing  
Publisher:  Society for Industrial and Applied Mathematics  
ISSN:  00975397  
Official Date:  2009  
Dates: 


Volume:  Volume 38  
Number:  Number 6  
Page Range:  pp. 24992510  
Identification Number:  10.1137/070681831  
Status:  Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Restricted or Subscription Access  
Funder:  National Science Foundation (U.S.) (NSF), Deutsche Forschungsgemeinschaft (DFG), Engineering and Physical Sciences Research Council (EPSRC)  
Grant number:  CCR0313219 (NSF), EP/D063191/1 (EPSRC), 0354600 (NSF), Me 872/83 (DFG)  
Version or Related Resource:  A preliminary version of this paper, entitled “On testable properties in bounded degree graphs,” authored by the first and third authors, appeared in the Proceedings of the 18th Annual Symposium on Discrete Algorithms (SODA), New Orleans, LA, 2007, pp. 494–501.  
References:  [1] N. Alon, E. Fischer, I. Newman, and A. Shapira, A combinatorial characterization of the 

URI:  http://wrap.warwick.ac.uk/id/eprint/37021 
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
View Item 