The Library

Testing hereditary properties of nonexpanding bounded-degree graphs

Tools

Czumaj, Artur, Shapira, Asaf and Sohler, Christian. (2009) Testing hereditary properties of nonexpanding bounded-degree graphs. SIAM Journal on Computing, Volume 38 (Number 6). pp. 2499-2510. ISSN 0097-5397

Preview

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 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 well known that in the bounded-degree 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., 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, very few graph properties have been known to be testable with a constant number of queries for general graph classes in the bounded-degree 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:

0097-5397

Official Date:

2009

Dates:

Date	Event
2009	Published

Volume:

Volume 38

Number:

Number 6

Page Range:

pp. 2499-2510

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:

CCR-0313219 (NSF), EP/D063191/1 (EPSRC), 0354600 (NSF), Me 872/8-3 (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
testable graph properties: It’s all about regularity, in Proceedings of the 38th Annual ACM
Symposium on Theory of Computing (STOC), ACM, New York, 2006, pp. 251–260.
[2] N. Alon, P. Seymour, and R. Thomas, A separator theorem for graphs with an excluded
minor and its applications, in Proceedings of the 27th Annual ACM Symposium on Theory
of Computing (STOC), ACM, New York, 1990, pp. 293–299.
[3] N. Alon and A. Shapira, Every monotone graph property is testable, in Proceedings of the
37th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 2005,
pp. 128–137.
[4] N. Alon and A. Shapira, A characterization of the (natural) graph properties testable with
one-sided error, SIAM J. Comput., 37 (2008), pp. 1703–1727.
[5] N. Alon and A. Shapira, A separation theorem in property testing, Combinatorica, 28 (2008),
pp. 261–281.
[6] M. A. Bender and D. Ron, Testing properties of directed graphs: Acyclicity and connectivity,
Random Structures Algorithms, 20 (2002), pp. 184–205.
[7] A. Bogdanov, K. Obata, and L. Trevisan, A lower bound for testing 3-colorability in
bounded-degree graphs, in Proceedings of the 43rd IEEE Symposium on Foundations of
Computer Science (FOCS), IEEE, Los Alamitos, CA, 2002, pp. 93–102.
[8] C. Borgs, J. Chayes, L. Lovasz, V. T. S ´ os, B. Szegedy, and K. Vesztergombi ´ , Graph
limits and parameter testing, in Proceedings of the 38th Annual ACM Symposium on
Theory of Computing (STOC), ACM, New York, 2006, pp. 261–270.
[9] A. Czumaj and C. Sohler, Abstract combinatorial programs and eﬃcient property testers,
SIAM J. Comput., 34 (2005), pp. 580–615.
[10] A. Czumaj and C. Sohler, Sublinear-time algorithms, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 89 (2006), pp. 23–47.
[11] E. Fischer, The art of uninformed decisions: A primer to property testing, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 75 (2001), pp. 97–126.
[12] J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan, A separator theorem for graphs of bounded genus, J. Algorithms, 5 (1984), pp. 391–407.
[13] O. Goldreich, Property testing in massive graphs, in Handbook of Massive Data Sets, J. Abello, P. M. Pardalos, and M. G. C. Resende, eds., Kluwer Academic Publishers, Dordrecht, 2002, pp. 123–147.
[14] O. Goldreich and D. Ron, A sublinear bipartiteness tester for bounded degree graphs, Combinatorica, 19 (1999), pp. 335–373.
[15] O. Goldreich and D. Ron, Property testing in bounded degree graphs, Algorithmica, 32 (2002), pp. 302–343.
[16] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, London, UK, 1980.
[17] R. Kumar and R. Rubinfeld, Sublinear time algorithms, SIGACT News, 34 (2003), pp. 57–67.
[18] R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math., 36 (1979), pp. 177–189.
[19] J. L. Ramirez-Alfonsin and B. A. Reed, eds., Perfect Graphs, John Wiley and Sons, New York, 2001.
[20] D. Ron, Property testing, in Handbook of Randomized Computing, Vol. II, P. M. Pardalos, S. Rajasekaran, J. Reif, and J. D. P. Rolim, eds., Kluwer Academic Publishers, Dordrecht, 2001, pp. 597–649.