Testing graphs for colorable properties

ABSTRACT

Let P be a property of graphs. An ∈-test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or not, distinguishes, with high probability, between the case of G satisfying P and the case that it has to be modified by adding and removing more than ∈(^{n 2}) edges to make it satisfy P. The property P is called testable, if for every ∈ there exists an ∈-test for P whose total number of queries is independent of the size of the input graph. Goldreich, Goldwasser and Ron [7] showed that certain graph properties, like k-colorability, admit an ∈-test. In [2] a first step towards a logical characterization of the testable graph properties was made by proving that all first order properties of type “∃∀” are testable while there exist first order graph properties of type “∀∃” which are not testable. For proving the positive part, it was shown that all properties describable by a very general type of coloring problem are testable.

While this result is tight from the standpoint of first order expressions, further steps towards the characterization of the testable graph properties can be taken by considering the coloring problem instead. It is proven here that other classes of graph properties, describable by various generalizations of the coloring notion used in [2], are testable, showing that this approach can broaden the understanding of the nature of the testable graph properties. The proof combines some generalizations of the methods used in [2] with additional methods.

REFERENCES

• 1: 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]
• 2: N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, Efficient testing of large graphs, Proceedings of the 40 th IEEE FOCS (1999), 656-666.
• 3: N. Alon and J. Spencer, The Probabilistic Method, Wiley (1992).
• 4: Bela Bollobas, Extremal Graph Theory, Dover Publications, Incorporated, 2004
• 5: A. Czygrinow , S. Poljak , V. Rödl, Constructive Quasi-Ramsey Numbers and Tournament Ranking, SIAM Journal on Discrete Mathematics, v.12 n.1, p.48-63, Jan. 1999 [doi>10.1137/S0895480197318301]
• 6: A. Frieze, The regularity lemma and approximation schemes for dense problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.12, October 14-16, 1996
• 7: 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]
• 8: W. T. Gowers, Lower bounds of tower type for Szemer6di's Uniformity Lemma, Geometric and Functional Analysis 7 (1997), 322-337.
• 9: J. Komlos and M. Simonovits, Szemeredi's Regularity Lemma and its applications in graph theory, In: Combinatorics, Paul ErdSs is Eighty, Vol II (D. Miklos, V. T. Sos, T. Szonyi eds.), Janos Bolyai Math. Soc., Budapest (1996), 295-352.
• 10: V. Rodl and R. Duke, On graphs with small subgraphs of large chromatic number, Graphs and Combinatorics 1 (1985), 91-96.
• 11: 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]
• 12: E. Szemeredi, Regular partitions of graphs, In: Proe. Colloque Inter. CNRS No. 260 (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

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, Verification