Testing versus estimation of graph properties

ABSTRACT

The topic of tolerant property testing, that of distinguishing input instances that are far from satisfying a property from those that are close enough to satisfying it (as opposed to distinguishing the far instances only from the satisfying instances), has recently become an active topic of research in the field of combinatorial property testing [13]. In the general setting, there exist properties that are testable but not tolerantly testable [10]. However, we show here that in the setting of the dense graph model, all testable properties are not only tolerantly testable, but also admit a constant query size algorithm that estimates the distance from the property up to any fixed additive constant.In the course of the construction of this algorithm we develop a framework for extending Szemerédi's Regularity Lemma, both as a prerequisite for formulating what kind of information about the input graph will provide us with the correct estimation, and as the means for efficiently gathering this information. This work is also connected to the question of finding a combinatorial characterization of the testable graph properties, and to the question of efficiently finding a regular partition.

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, Combinatorica 20 (2000), 451--476.
• 3: Noga Alon , Asaf Shapira, Every monotone graph property is testable, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060611]
• 4: N. Alon and A. Shapira, private communication.
• 5: Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
• 6: R. Diestel, Graph Theory (2nd edition), Springer (2000).
• 7: 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
• 8: E. Fischer, The art of uninformed decisions: A primer to property testing, The Bulletin of the European Association for Theoretical Computer Science 75 (2001), 97--126.
• 9: Eldar Fischer, The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance, SIAM Journal on Computing, v.34 n.5, p.1147-1158, 2005 [doi>10.1137/S009753970445603]
• 10: Eldar Fischer , Lance Fortnow, Tolerant Versus Intolerant Testing for Boolean Properties, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, p.135-140, June 11-15, 2005 [doi>10.1109/CCC.2005.30]
• 11: 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]
• 12: 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]
• 13: M. Parnas, D. Ron and R. Rubinfeld, Tolerant property testing and distance approximation, available as ECCC Report TR04-010.
• 14: D. Ron, Property testing (a tutorial), In: Handbook of Randomized Computing (S. Rajasekaran, P. M. Pardalos, J. H. Reif and J. D. P. Rolim eds), Kluwer Press (2001).
• 15: 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]
• 16: E. Szemerédi, Regular partitions of graphs, In: Proc. Colloque Inter. CNRS No. 260 (J. C. Bermond, J. C. Fournier, M. Las Vergnas and D. Sotteau eds.), 2978, 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

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Theory

Keywords:
distance approximation, graph properties, property testing, regularity lemma