Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
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 …