Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
Noga Alon, Eldar Fischer, Ilan Newman · SIAM Journal on Computing · 2007
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 $\epsilon$-testable. However, the complexity of the test is double-tower with respect to $1/\epsilon$, 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 $\epsilon$-testable, with a number of queries that is polynomial in $1/\epsilon$. Our main tool is a new “conditional” version of the regularity lemma for binary matrices, which may be interesting on its own.