Efficient testing of bipartite graphs for forbidden induced subgraphs

Noga Alon, Eldar Fischer, Ilan Newman

Research output: Contribution to journalArticle

22 Scopus citations

Abstract

Alon et. al. [N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 (2000), pp. 451-476] showed that every property that is characterized by a finite collection of forbidden induced subgraphs is ε-testable. However, the complexity of the test is double-tower with respect to 1/ε, as the only tool known to construct such tests uses a variant of Szemerédi's regularity lemma. Here we show that any property of bipartite graphs that is characterized by a finite collection of forbidden induced subgraphs is ε-testable, with a number of queries that is polynomial in 1/ε. Our main tool is a new "conditional" version of the regularity lemma for binary matrices, which may be interesting on its own.

Original languageEnglish (US)
Pages (from-to)959-976
Number of pages18
JournalSIAM Journal on Computing
Volume37
Issue number3
DOIs
StatePublished - Dec 1 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Approximation
  • Graph algorithms
  • Property testing
  • Regularity lemma

Fingerprint Dive into the research topics of 'Efficient testing of bipartite graphs for forbidden induced subgraphs'. Together they form a unique fingerprint.

Cite this