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.
All Science Journal Classification (ASJC) codes
- Computer Science(all)
- Graph algorithms
- Property testing
- Regularity lemma