research-article

Every minor-closed property of sparse graphs is testable

Authors:

Itai Benjamini,

Asaf ShapiraAuthors Info & Claims

STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

Pages 393 - 402

https://doi.org/10.1145/1374376.1374433

Published: 17 May 2008 Publication History

Abstract

Testing a property P of graphs in the bounded degree model deals with the following problem: given a graph G of bounded degree d we should distinguish (with probability 0.9, say) between the case that G satisfies P and the case that one should add/remove at least ε d n edges of G to make it satisfy P. In sharp contrast to property testing of dense graphs, which is relatively well understood, very few properties are known to be testable in bounded degree graphs with a constant number of queries. In this paper we identify for the first time a large (and natural) family of properties that can be efficiently tested in bounded degree graphs, by showing that every minor-closed graph property can be tested with a constant number of queries. As a special case, we infer that many well studied graph properties, like being planar, outer-planar, series-parallel, bounded genus, bounded tree-width and several others, are testable with a constant number of queries. None of these properties was previously known to be testable even with o(n) queries. The proof combines results from the theory of graph minors with results on convergent sequences of sparse graphs, which rely on martingale arguments.

References

[1]

N. Alon, E. Fischer, I. Newman and A. Shapira, A combinatorialcharacterization of the testable graph properties: it's all aboutregularity, Proc. of STOC'06, 251--260. Also, SIAM J. on Computing,to appear.

Digital Library

[2]

N. Alon, P. D. Seymour and R. Thomas, A separator theorem fornon-planar graphs, J. Amer. Math. Soc. 3 (1990), 801--808.

[3]

N. Alon and A. Shapira, A characterization of the (natural) graphproperties testable with one-sided error, Proc. of FOCS 2005,429--438. Also, SIAM J. on Computing, to appear.

Digital Library

[4]

N. Alon and A. Shapira, Homomorphisms in graph property testing,in Topics in discrete mathematics, 281--313, Springer, Berlin,2006.

[5]

N. Alon and A. Shapira, A separation theorem in property testing,Combinatorica, to appear.

Digital Library

[6]

M. Blum, M. Luby and R. Rubinfeld, Self-testing/correcting withapplications to numerical problems, JCSS 47 (1993), 549--595.

Digital Library

[7]

H. L. Bodlaender, Discovering treewidth, Lecture Notes in ComputerScience, 3381 (2005), 1--16.

Digital Library

[8]

A. Bogdanov, K. Obata, and L. Trevisan, A lower bound for testing3-colorability in bounded-degree graphs, FOCS 2002, 93--102.

Digital Library

[9]

C. Borgs, J. Chayes, L. Lovász, V. T. Sos, B. Szegedy, andK. Vesztergombi, Graph limits and parameter testing,STOC 2006, 261--270.

Digital Library

[10]

A. Czumaj, A. Shapira, and C. Sohler, Testing hereditary propertiesof non-expanding bounded-degree graphs, submitted (full version of CS1).

[11]

A. Czumaj and C. Sohler, Testing expansion in bounded-degree graphs,Proc. of FOCS 2007, 570-578.

Digital Library

[12]

A. Czumaj and C. Sohler, Sublinear-time algorithms, Bulletin of theEATCS, 89 (2006) 23--47.

[13]

A. Czumaj and C. Sohler, On testable properties in bounded degreegraphs, Proc. of SODA 2007, 494--501.

Digital Library

[14]

E. Demaine, M. Hajiaghayi and K. Kawarabayashi, Algorithmic graphminor theory: decomposition, approximation, and coloring, Proc. of FOCS 2005, 637-646.

Digital Library

[15]

R. Diestel, Graph Theory (Third Edition), Springer, Heidenberg, 2005.

[16]

C. Domingo and J. Shawe-Taylor, The Complexity of LearningMinor-Closed Graph Classes, Proc. of Algorithmic Learning Theory1995, 249--260.

Digital Library

[17]

R. Downey and M. Fellows, Parameterized Complexity, Springer,1999.

[18]

G. Elek, The combinatorial cost, to appear in L'Enseignement Mathématique

[19]

G. Elek, A Regularity lemma for bounded degree graphs and itsapplications: parameter testing and infinite volume limits,arXiv:07112800, 2007.

[20]

E. Fischer, The art of uninformed decisions: A primer to propertytesting, The Computational Complexity Column of The Bulletin ofthe European Association for Theoretical Computer Science 75(2001), 97--126.

[21]

O. Goldreich, S. Goldwasser and D. Ron, Property testing and itsconnection to learning and approximation, J. of the ACM 45(4):653--750 (1998).

Digital Library

[22]

O. Goldreich and D. Ron, Property Testing in Bounded-Degree Graphs,Algorithmica 32 (2002), 302--343.

Digital Library

[23]

O. Goldreich and D. Ron, A sublinear bipartiteness tester forbounded degree graphs, Combinatorica, 19 (1999), 335--373.

[24]

O. Goldreich and L. Trevisan, Three theorems regarding testing graph properties, Random Structures and Algorithms, 23(1):23--57, 2003.

Digital Library

[25]

J. E. Hopcroft and R. E. Tarjan, Efficient planarity testing, J. of the ACM, 21 (1974), 549--568.

Digital Library

[26]

A. Kostochka, The minimum Hadwiger number for graphs with a givenmean degree of vertices, Metody Diskret. Analliz. 38 (1982), 37--58{in Russion}.

[27]

A. Kostochka, A lower bound for the Hadwiger number of graphs bytheir average degree, Combinatorica, 4 (1984), 307--316.

[28]

K. Kuratowski, Sur le problème des courbes gauches en topologie,Fund. Math. 15: 271--283.

[29]

R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs,SIAM J. Appl. Math., 36 (1979), 177--189.

Digital Library

[30]

R. J. Lipton and R. E. Tarjan, Applications of a planar separatortheorem, SIAM J. on Computing 9 (1980), 615--627.

[31]

L. Lovász, Graph minor theory, Bull. Amer. Math. Soc. 43 (2006),no. 1, 75--86.

[32]

M. Parnas and D. Ron, Testing the diameter of graphs, Randomstructures and algorithms, 20 (2002), 165--183.

Digital Library

[33]

N. Robertson and P.D. Seymour: Graph minors XIII. The disjoint paths problem, J. Combin.Theory Ser. B 63 (1995), 65--110.

Digital Library

[34]

N. Robertson and P. D. Seymour, Graph minors. XX. Wagner's Conjecture, J. Combin. Theory Ser. B 92 (2004), 325--357.

Digital Library

[35]

R. Rubinfeld, Sublinear time algorithms, in International Congress of Mathematicians. Vol. III,1095--1110, Eur. Math. Soc., Zürich, 2006.

[36]

. Ron,Property testing, in: P. M. Pardalos, S. Rajasekaran, J. Reif andJ. D. P. Rolim, editors, Handbook of Randomized Computing,Vol. II, Kluwer Academic Publishers, 2001, 597--649.

[37]

. Rubinfeld and M. Sudan,Robust characterization of polynomials with applications to programtesting, SIAM J. on Computing, 25 (1996), 252--271.

Digital Library

[38]

O. Schramm, Graph sequences with hyperfinite limits are hyperfinite, ar Xiv:0711.3808, 2007.

[39]

. Szemerédi,Regular partitions of graphs, In: Proc. Colloque Inter. CNRS (J. C. Bermond, J. C. Fournier, M. Las Vergnas andD. Sotteau, eds.), 1978, 399--401.

[40]

A. Thomason, An extremal function for contractions of graphs, Math. Proc. Cambridge Philos. Soc. 95 (1984), 261--265.

[41]

A. Thomason, The extremal function for complete minors, J. of Combinatorial Theory Series B, 81 (2001), 318--338.

Digital Library

[42]

K. Wagner, Über eine eigenschaft der ebenen komplexe, Math. Ann. 114 (1937), 570--590.

Cited By

Romero MWrochna MŽivný S(2023)Pliability and Approximating Max-CSPsJournal of the ACM10.1145/362651570:6(1-43)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3626515
Chen XRandolph TServedio RSun T(2022)A Lower Bound on Cycle-Finding in Sparse DigraphsACM Transactions on Algorithms10.1145/341797918:4(1-23)Online publication date: 10-Oct-2022
https://dl.acm.org/doi/10.1145/3417979
Kumar ASeshadhri CStolman A(2022)Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree GraphsSIAM Journal on Computing10.1137/20M131282452:2(STOC19-323-STOC19-338)Online publication date: 16-Aug-2022
https://doi.org/10.1137/20M1312824
Show More Cited By

Index Terms

Every minor-closed property of sparse graphs is testable
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Every property of hyperfinite graphs is testable
STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

A property testing algorithm for a property Π in the bounded degree graph model[7] is an algorithm that, given access to the adjacency list representation of a graph G=(V,E) with maximum degree at most d, accepts G with probability at least 2/3 if G has ...
Every monotone graph property is testable
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

A graph property is called monotone if it is closed under taking (not necessarily induced) subgraphs (or, equivalently, if it is closed under removal of edges and vertices). Many monotone graph properties are some of the most well-studied properties in ...
Every Property of Hyperfinite Graphs Is Testable
^† Special Section on the Forty-Second Annual ACM Symposium on Theory of Computing (STOC 2010)

A $k$-disc around a vertex $v$ of a graph $G=(V,E)$ is the subgraph induced by all vertices of distance at most $k$ from $v$. We show that the structure of a planar graph on $n$ vertices, and with constant maximum degree $d$, is determined, up to the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

May 2008

712 pages

ISBN:9781605580470

DOI:10.1145/1374376

General Chair:
Richard Ladner
University of Washington
,
Program Chair:
Cynthia Dwork
Microsoft Research, Silicon Valley

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 May 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '08

Sponsor:

STOC '08: Symposium on Theory of Computing

May 17 - 20, 2008

British Columbia, Victoria, Canada

Acceptance Rates

STOC '08 Paper Acceptance Rate 80 of 325 submissions, 25%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

63
Total Citations
View Citations
320
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)4

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Romero MWrochna MŽivný S(2023)Pliability and Approximating Max-CSPsJournal of the ACM10.1145/362651570:6(1-43)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3626515
Chen XRandolph TServedio RSun T(2022)A Lower Bound on Cycle-Finding in Sparse DigraphsACM Transactions on Algorithms10.1145/341797918:4(1-23)Online publication date: 10-Oct-2022
https://dl.acm.org/doi/10.1145/3417979
Kumar ASeshadhri CStolman A(2022)Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree GraphsSIAM Journal on Computing10.1137/20M131282452:2(STOC19-323-STOC19-338)Online publication date: 16-Aug-2022
https://doi.org/10.1137/20M1312824
Kumar ASeshadhri CStolman A(2022)Random walks and forbidden minors III: $\text{poly}\left(d\varepsilon ^{-1}\right)$-time partition oracles for minor-free graph classes2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00034(257-268)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00034
Romero MWrochna MŽivný SMarx D(2021)Treewidth-pliability and PTAS for max-CSPsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458093(473-483)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458093
Levi RMedina MRon D(2020)Property testing of planarity in the CONGEST modelDistributed Computing10.1007/s00446-020-00382-3Online publication date: 13-Jul-2020
https://doi.org/10.1007/s00446-020-00382-3
ITO HNAGAO APARK T(2019)Generalized Shogi, Chess, and Xiangqi are Constant-Time TestableIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.E102.A.1126E102.A:9(1126-1133)Online publication date: 1-Sep-2019
https://doi.org/10.1587/transfun.E102.A.1126
Kumar ASeshadhri CStolman ACharikar MCohen E(2019)Random walks and forbidden minors IIProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316330(559-567)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316330
Goldreich OCharikar MCohen E(2019)Testing graphs in vertex-distribution-free modelsProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316302(527-534)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316302
Ito H(2019)What Graph Properties Are Constant-Time Testable?The Review of Socionetwork Strategies10.1007/s12626-019-00054-0Online publication date: 25-Sep-2019
https://doi.org/10.1007/s12626-019-00054-0
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents