The difficulty of testing for isomorphism against a graph that is given in advance

ABSTRACT

Motivated by a question from [6], we investigate the number of queries required for testing that an input graph G is isomorphic to a graph H that is given in advance. Our main result is that the more "complex" H is, the more queries it takes to test an input graph G for the property of being isomorphic to H. This is provided in terms of an upper bound and a lower bound on the number of queries, giving a relation between this number and a natural measure of the complexity of H.

REFERENCES

• 1: N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, Efficient testing of large graphs, Combinatorica 20 (2000), 451--476.
• 2: N. Alon and J. H. Spencer, The probabilistic method. Wiley-Interscience (John Wiley & Sons), New York, 1992 (1st edition) and 2000 (2nd edition).
• 3: 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]
• 4: 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
• 5: 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.
• 6: Eldar Fischer , Guy Kindler , Dana Ron , Shmuel Safra , Alex Samorodnitsky, Testing Juntas, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.103-112, November 16-19, 2002
• 7: Eldar Fischer , Ilan Newman, Testing of matrix properties, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.286-295, July 2001, Hersonissos, Greece [doi>10.1145/380752.380812]
• 8: 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]
• 9: 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]
• 10: 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).
• 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. 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.), 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:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory

Keywords:
graph isomorphism, property testing, regularity lemma