Random walks and forbidden minors II: a poly( d ε -1 )-query tester for minor-closed properties of bounded degree graphs
Random walks and forbidden minors II: a poly( d ε -1 )-query tester for minor-closed properties of bounded degree graphs
复制标题
随机游走和禁止未成年人 II：有界度图的未成年人封闭性质的 Poly( d ε -1 ) 查询测试器
DOI：
10.1145/3313276.3316330
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Stolman, Andrew
中科院分区：
文献类型：
--
作者：
Kumar, Akash;Seshadhri, C.;Stolman, Andrew
设 G 是一个具有 n 个顶点和最大度数的图。修复一些次要闭合属性P（例如平面度）。如果必须移除 εdn 边缘才能使其具有 P，我们就说 G 是 ε-远离 P。 Benjamini-Schramm-Shapira (STOC 2008) 的开创性工作中引入了属性测试 P 的问题，该工作为测试人员提供了 ε−1 中的三指数查询复杂度。 Levi-Ron (TALG 2015) 给出了迄今为止最好的测试器，具有拟多项式（ε−1）查询复杂性。即使对于平面性，获得查询复杂度为 (dε−1) 的属性测试器也是一个悬而未决的问题。在本文中，我们解决了这个悬而未决的问题。对于任何小闭属性，我们给出一个查询复杂度为· (ε−1) 的测试器。之前关于（独立于双边）测试器的工作主要是组合的。另一方面，我们的工作采用了谱图理论的技术。本文是作者最近工作（FOCS 2018）的延续，分析了发现禁止未成年人的随机游走算法。
LetGbe a graph withnvertices and maximum degreed. Fix some minor-closed propertyP(such as planarity). We say thatGis ε-far fromPif one has to remove εdnedges to make it haveP. The problem of property testingPwas introduced in the seminal work of Benjamini-Schramm-Shapira (STOC 2008) that gave a tester with query complexity triply exponential in ε−1. Levi-Ron (TALG 2015) have given the best tester to date, with a quasipolynomial (in ε−1) query complexity. It is an open problem to get property testers whose query complexity is (dε−1), even for planarity.In this paper, we resolve this open question. For any minor-closed property, we give a tester with query complexityd· (ε−1). The previous line of work on (independent ofn, two-sided) testers is primarily combinatorial. Our work, on the other hand, employs techniques from spectral graph theory. This paper is a continuation of recent work of the authors (FOCS 2018) analyzing random walk algorithms that find forbidden minors.