A characterization of easily testable induced subgraphs

ABSTRACT

Let H be a fixed graph on h vertices. We say that a graph G is induced H-free if it does not contain any induced copy of H. Let G be a graph on n vertices and suppose that at least εn² edges have to be added to or removed from it in order to make it induced H-free. It was shown in [5] that in this case G contains at least f(ε, h)n^h induced copies of H, where 1/f(ε, h) is an extremely fast growing function in 1/ε, that is independent of n. As a consequence, it follows that for every H, testing induced H-freeness with one-sided error has query complexity independent of n. A natural question, raised by the first author in [1], is to decide for which graphs H the function 1/f(ε, H) can be bounded from above by a polynomial in 1/ε. An equivalent question is for which graphs H, can one design a one-sided error property tester for testing induced H-freeness, whose query complexity is polynomial in 1/ε. We settle this question almost completely by showing that, quite surprisingly, for any graph other than the paths of lengths 1,2 and 3, the cycle of length 4, and their complements, no such property tester exists. We further show that a similar result also applies to the case of directed graphs, thus answering a question raised by the authors in [9]. We finally show that the same results hold even in the case of two-sided error property testers. The proofs combine combinatorial, graph theoretic and probabilistic arguments with results from additive number theory.

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: Noga Alon , W. Fernandez de la Vega , Ravi Kannan , Marek Karpinski, Random sampling and approximation of MAX-CSP problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509945]
• 4: N. Alon , S. Dar , M. Parnas , D. Ron, Testing of clustering, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.240, November 12-14, 2000
• 5: Efficient Testing of Large Graphs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.1, October 17-18, 1999
• 6: 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]
• 7: Noga Alon , Michael Krivelevich, Testing k-colorability, SIAM Journal on Discrete Mathematics, v.15 n.2, p.211-227, 2002 [doi>10.1137/S0895480199358655]
• 8: 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]
• 9: 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]
• 10: F. A. Behrend, On sets of integers which contain no three terms in arithmetic progression, Proc. National Academy of Sciences USA 32 (1946), 331--332.
• 11: Andrej Bogdanov , Kenji Obata , Luca Trevisan, A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.93-102, November 16-19, 2002
• 12: B. Bollobás, P. Erdös, M. Simonovits and E. Szemerédi, Extremal graphs without large forbidden subgraphs, Annals of Discrete Mathematics 3 (1978), 29--41.
• 13: D. G. Corneil, H. Lerchs, L. Stewart Burlingham, Complement Reducible Graphs, Discrete Applied Mathematics 3 (1981), 163--174.
• 14: D. G. Corneil, Y. Perl and L. K. Stewart, A linear recognition algorithm for cographs, SIAM J. Comput. 14 (1985), 926--934.
• 15: Artur Czumaj , Christian Sohler, Testing Hypergraph Coloring, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.493-505, July 08-12, 2001
• 16: Artur Czumaj , Christian Sohler , Martin Ziegler, Property Testing in Computational Geometry, Proceedings of the 8th Annual European Symposium on Algorithms, p.155-166, September 05-08, 2000
• 17: P. Erdös, 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.
• 18: 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.
• 19: 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
• 20: Eldar Fischer , Eric Lehman , Ilan Newman , Sofya Raskhodnikova , Ronitt Rubinfeld , Alex Samorodnitsky, Monotonicity testing over general poset domains, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509977]
• 21: A. Frieze and R. Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), 175--220.
• 22: O. Goldreich, Combinatorial property testing - a survey, In: Randomization Methods in Algorithm Design (P. Pardalos, S. Rajasekaran and J. Rolim eds.), AMSDIMACS (1998), 45--60.
• 23: O. Goldreich , S. Goldwasser , D. Ron, Property testing and its connection to learning and approximation, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.339, October 14-16, 1996
• 24: O. Goldreich , L. Trevisan, Three Theorems Regarding Testing Graph Properties, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.460, October 14-17, 2001
• 25: R. L. Graham, B. L. Rothschild and J. H. Spencer, Ramsey Theory, Second Edition, Wiley, New York, 1990.
• 26: T. A. McKee and F.R. McMorris, Topics in Intersection Graph Theory, SIAM, Philadelphia, PA, 1999.
• 27: V. Rödl and R. Duke, On graphs with small subgraphs of large chromatic number, Graphs and Combinatorics 1 (1985), 91--96.
• 28: D. Ron, 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.
• 31: A. C. Yao, Probabilistic computation, towards a unified measure of complexity, Proc. of the 18th IEEE FOCS (1977), 222--227.