Every minor-closed property of sparse graphs is testable
Every minor-closed property of sparse graphs is testable
复制标题
稀疏图的每个小闭性质都是可测试的
DOI：
10.1145/1374376.1374433
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
A. Shapira
中科院分区：
文献类型：
--
作者：
I. Benjamini;O. Schramm;A. Shapira
在有界度模型中测试图的属性P处理以下问题：给定一个有界度为d的图G，我们应该区分（比如说，概率为0.9）在G满足P的情况和应该添加/删除G的至少ε d n条边以使其满足P的情况之间。与相对较好理解的稠密图的属性测试形成鲜明对比，已知在具有恒定数量的查询的有界度图中可测试的属性很少。在本文中，我们首次确定了一个大的（和自然的）家庭的属性，可以有效地测试有界度图，通过显示，每个小的封闭图形属性可以测试一个常数数量的查询。作为一个特殊的情况下，我们推断，许多良好的研究图形的属性，如平面，外平面，串行并行，有界属，有界树宽度和其他几个，是可测试的一个常数数量的查询。这些属性以前都不知道是可测试的，即使是O（n）查询。证明结合的结果，从理论的图未成年人的结果收敛序列的稀疏图，这依赖于鞅参数。
Testing a property P of graphs in the bounded degree model deals with the following problem: given a graph G of bounded degree d we should distinguish (with probability 0.9, say) between the case that G satisfies P and the case that one should add/remove at least ε d n edges of G to make it satisfy P. In sharp contrast to property testing of dense graphs, which is relatively well understood, very few properties are known to be testable in bounded degree graphs with a constant number of queries. In this paper we identify for the first time a large (and natural) family of properties that can be efficiently tested in bounded degree graphs, by showing that every minor-closed graph property can be tested with a constant number of queries. As a special case, we infer that many well studied graph properties, like being planar, outer-planar, series-parallel, bounded genus, bounded tree-width and several others, are testable with a constant number of queries. None of these properties was previously known to be testable even with o(n) queries. The proof combines results from the theory of graph minors with results on convergent sequences of sparse graphs, which rely on martingale arguments.