Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
复制标题
禁止诱导子图的二部图的高效测试
DOI：
10.1137/050627915
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
I. Newman
中科院分区：
文献类型：
--
作者：
N. Alon;E. Fischer;I. Newman
Alon et. [N. Alon，E.菲舍尔，M。Krivelevich和M. Szegedy，Combinatorica，20（2000），pp. 451-476]证明了由禁止导出子图的有限集合所表征的每一个性质都是$\n $-可测试的。然而，测试的复杂性是关于1/\n $的双塔，因为已知构造此类测试的唯一工具使用Szemeredi正则性引理的变体。在这里，我们表明，任何性质的二分图，其特征在于由一个有限的禁止诱导子图的集合是$\n $-可测试的，与一些查询是多项式在$1/\n $。我们的主要工具是一个新的“条件”版本的二进制矩阵的正则性引理，这可能是有趣的本身。
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 Szemeredi'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.