The complexity of testing all properties of planar graphs, and the role of isomorphism
The complexity of testing all properties of planar graphs, and the role of isomorphism
复制标题
测试平面图所有属性的复杂性以及同构的作用
DOI：
10.1137/1.9781611977073.69
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
C. Seshadhri
中科院分区：
文献类型：
--
作者：
Sabyasachi Basu;Akash Kumar;C. Seshadhri
考虑在有界度图上的属性测试，并让k> 0表示邻近参数。Newman-Sohler（SICOMP 2013）的一个著名定理断言，平面图（更一般地说是超有限的）的所有性质都是可测试的，查询复杂度仅取决于k。最近在测试minor-freeness方面的进展已经证明，平面图的所有可加性和单调性都可以在poly（n-1）查询中测试。一些不属于这类的性质，如哈密尔顿性，对于平面图也有类似的复杂性。受这些结果的启发，我们问：可以所有的属性，平面图可以测试在聚（N-1）查询？所有的平面属性是否都有一个统一的查询复杂度上限，什么是“最难”测试的属性？我们发现了一个令人惊讶的干净和最佳答案。有界度平面图的任何性质都可以在exp（O（n-2））查询中测试。此外，有一个匹配的下限，直到常数因子的指数。测试与固定图同构的自然属性需要exp（Ω（Ω-2））查询，从而表明与显式固定图同构（直到多项式依赖）是平面图的最难属性。上界是纽曼-索勒分析的直接改编，更仔细地跟踪了对cnt的依赖性。主要的技术贡献是下界的构造，这是由一个特殊的家庭的平面图，都是相互远离对方。我们也可以应用我们的技术得到类似的结果，有界树宽图。我们证明了有界树宽图的所有性质都可以在exp（O（n-1 log n-1））查询中测试。此外，测试与固定森林的同构需要exp（Ω（Ω-1））查询。
Consider property testing on bounded degree graphs and let∊> 0 denote the proximity parameter. A remarkable theorem of Newman-Sohler (SICOMP 2013) asserts thatallproperties of planar graphs (more generally hyperfinite) are testable with query complexity only depending on∊. Recent advances in testing minor-freeness have proven that all additive and monotone properties of planar graphs can be tested in poly(∊–1) queries. Some properties falling outside this class, such as Hamiltonicity, also have a similar complexity for planar graphs. Motivated by these results, we ask: can all properties of planar graphs can be tested in poly(∊–1) queries? Is there a uniform query complexity upper bound for all planar properties, and what is the “hardest” such property to test?We discover a surprisingly clean and optimal answer. Any property of bounded degree planar graphs can be tested in exp(O(∊–2)) queries. Moreover, there is a matching lower bound, up to constant factors in the exponent. The natural property of testing isomorphism to a fixed graph requires exp(Ω(∊–2)) queries, thereby showing that (up to polynomial dependencies) isomorphism to an explicit fixed graph is the hardest property of planar graphs. The upper bound is a straightforward adaptation of the Newman-Sohler analysis that tracks dependencies on∊more carefully. The main technical contribution is the lower bound construction, which is achieved by a special family of planar graphs that are all mutually far from each other.We can also apply our techniques to get analogous results for bounded treewidth graphs. We prove that all properties of bounded treewidth graphs can be tested in exp(O(∊–1log∊–1)) queries. Moreover, testing isomorphism to a fixed forest requires exp(Ω(∊–1)) queries.
登录
查看更多内容
稀疏图的每个小闭性质都是可测试的
DOI：
10.1145/1374376.1374433
发表时间：
2008
期刊：
Proceedings of the fortieth annual ACM symposium on Theory of computing
影响因子：
--
作者：
I. Benjamini;O. Schramm;A. Shapira
通讯作者：
A. Shapira
具有单边误差的一般平面图的可测试图属性的表征（都是关于禁止子图）
DOI：
10.1109/focs.2019.00089
发表时间：
2019
期刊：
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
A. Czumaj;C. Sohler
通讯作者：
C. Sohler
DOI：
10.1007/978-3-642-22935-0_45
发表时间：
2011
期刊：
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
A. Edelman;Avinatan Hassidim;H. N. Nguyen;Krzysztof Onak
通讯作者：
Krzysztof Onak
在无次要图中测试哈密顿性（和其他问题）
DOI：
10.4230/lipics.approx/random.2021.61
发表时间：
2021
期刊：
ArXiv
影响因子：
--
作者：
Reut Levi;Nadav Shoshan
通讯作者：
Nadav Shoshan
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
Oded Goldreich
通讯作者：
Oded Goldreich