Every monotone graph property is testable

ABSTRACT

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 graph theory, and the abstract family of all monotone graph properties was also extensively studied. Our main result in this paper is that any monotone graph property can be tested with one-sided error, and with query complexity depending only on ε. This result unifies several previous results in the area of property testing, and also implies the testability of well-studied graph properties that were previously not known to be testable. At the heart of the proof is an application of a variant of Szemerédi's Regularity Lemma. The main ideas behind this application may be useful in characterizing all testable graph properties, and in generally studying graph property testing.As a byproduct of our techniques we also obtain additional results in graph theory and property testing, which are of independent interest. One of these results is that the query complexity of testing testable graph properties with one-sided error may be arbitrarily large. Another result, which significantly extends previous results in extremal graph-theory, is that for any monotone graph property P, any graph that is ε -far from satisfying P, contains a subgraph of size depending on ε only, which does not satisfy P. Finally, we prove the following compactness statement: If a graph G is ε-far from satisfying a (possibly infinite) set of graph properties P, then it is at least δ P ε-far from satisfying one of the properties.

REFERENCES

• 1: N. Alon, Testing Subgraphs in Large Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.434, October 14-17, 2001
• 2: N. Alon , R. A. Duke , H. Lefmann , V. Rödl , R. Yuster, The algorithmic aspects of the regularity lemma, Journal of Algorithms, v.16 n.1, p.80-109, Jan. 1994 [doi>10.1006/jagm.1994.1005 ]
• 3: Efficient Testing of Large Graphs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.1, October 17-18, 1999
• 4: Noga Alon , Michael Krivelevich , Ilan Newman , Mario Szegedy, Regular Languages are Testable with a Constant Number of Queries, SIAM Journal on Computing, v.30 n.6, p.1842-1862, 2001 [doi>10.1137/S0097539700366528]
• 5: Noga Alon , Michael Krivelevich, Testing k-colorability, SIAM Journal on Discrete Mathematics, v.15 n.2, p.211-227, 2002 [doi>10.1137/S0895480199358655]
• 6: Noga Alon , Asaf Shapira, Testing satisfiability, Journal of Algorithms, v.47 n.2, p.87-103, July 2003 [doi>10.1016/S0196-6774(03)00019-1]
• 7: Noga Alon , Asaf Shapira, Testing subgraphs in directed graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780644]
• 8: N. Alon and A. Shapira, Extremal graphs, recursive functions and a separation theorem in property-testing, manuscript.
• 9: N. Alon and J. H. Spencer, The probabilistic method, Second Edition, Wiley, New York, 2000.
• 10: József Balogh , Béla Bollobś , David Weinreich, Measures on monotone properties of graphs, Discrete Applied Mathematics, v.116 n.1-2, p.17-36, January 2002 [doi>10.1016/S0166-218X(01)00175-5 ]
• 11: D. Eichhorn and D. Mubayi, Edge-coloring cliques with many colors on subcliques, Combinatorica 20 (2000), 441--444.
• 12: P. Erdos, P. Frankl and V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin. 2 (1986) 113--121.
• 13: P. Erdos and A. Gyárfás, A variant of the classical Ramsey problem, Combinatorica 17 (1997), 459--467.
• 14: Eldar Fischer, Testing graphs for colorable properties, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.873-882, January 07-09, 2001, Washington, D.C., United States
• 15: E. Fischer, The art of uninformed decisions: A primer to property testing, The Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science 75 (2001), 97--126.
• 16: Eldar Fischer , Ilan Newman , Jiří Sgall, Functions that have read-twice constant width branching programs are not necessarily testable, Random Structures & Algorithms, v.24 n.2, p.175-193, March 2004 [doi>10.1002/rsa.10110]
• 17: E. Friedgut and G. Kalai, Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124 (1996), 2993--3002.
• 18: O. Goldreich, Combinatorial property testing - a survey, In: Randomization Methods in Algorithm Design (P. Pardalos, S. Rajasekaran and J. Rolim eds.), AMS-DIMACS (1998), 45--60.
• 19: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 20: Oded Goldreich , Luca Trevisan, Three theorems regarding testing graph properties, Random Structures & Algorithms, v.23 n.1, p.23-57, August 2003 [doi>10.1002/rsa.10078]
• 21: R. L. Graham, B. L. Rothschild and J. H. Spencer, Ramsey Theory, Second Edition, Wiley, New York, 1990.
• 22: W. T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, manuscript.
• 23: J. Komlós and M. Simonovits, Szemerédi's Regularity Lemma and its applications in graph theory. In: Combinatorics, Paul Erdös is Eighty, Vol II (D. Miklós, V. T. Sös, T. Szönyi eds.), János Bolyai Math. Soc., Budapest (1996), 295--352.
• 24: I. Newman, Testing of function that have small width branching programs, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.251, November 12-14, 2000
• 25: B. Nagle, V. Rödl and M. Schacht, The counting lemma for regular k-uniform hypegraphs, manuscript.
• 26: V. Rödl and R. Duke, On graphs with small subgraphs of large chromatic number, Graphs and Combinatorics 1 (1985), 91--96.
• 27: Vojtěch Rödl , Jozef Skokan, Regularity lemma for k-uniform hypergraphs, Random Structures & Algorithms, v.25 n.1, p.1-42, August 2004 [doi>10.1002/rsa.20017]
• 28: Property testing, in: P. M. Pardalos, S. Rajasekaran, J. Reif and J. D. P. Rolim, editors, Handbook of Randomized Computing, Vol. II, Kluwer Academic Publishers, 2001, 597--649.
• 29: Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]
• 30: E. Szemerédi, Regular partitions of graphs, In: Proc. Colloque Inter. CNRS (J. C. Bermond, J. C. Fournier, M. Las Vergnas and D. Sotteau, eds., 1978, 399--401.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
monotone properties, property testing, regularity lemma