A characterization of easily testable induced subgraphs

Noga Alon, Asaf Shapira

Research output: Contribution to journalArticle

47 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 C be a graph on n vertices and suppose that at least ∈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)nh 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)
Pages (from-to)791-805
Number of pages15
JournalCombinatorics Probability and Computing
Volume15
Issue number6
DOIs
StatePublished - Nov 1 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A characterization of easily testable induced subgraphs'. Together they form a unique fingerprint.

  • Cite this