A Characterization of Easily Testable Induced Subgraphs

Noga Mordechai Alon, Asaf Shapira

Research output: Contribution to conferencePaper

9 Scopus citations

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 en 2 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.

Original languageEnglish (US)
Pages935-944
Number of pages10
StatePublished - Apr 15 2004
Externally publishedYes
EventProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
Duration: Jan 11 2004Jan 13 2004

Other

OtherProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityNew Orleans, LA.
Period1/11/041/13/04

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A Characterization of Easily Testable Induced Subgraphs'. Together they form a unique fingerprint.

  • Cite this

    Alon, N. M., & Shapira, A. (2004). A Characterization of Easily Testable Induced Subgraphs. 935-944. Paper presented at Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA., United States.