Random walks and forbidden minors II: A poly(dε^-1)-query tester for minor-closed properties of bounded-degree graphs
share
Let G be a graph with n vertices and maximum degree d. Fix some minor-closed property P (such as planarity). We say that G is ε-far from P if one has to remove ε dn edges to make it have P. The problem of property testing P was 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 poly(dε^-1), even for planarity. In this paper, we resolve this open question. For any minor-closed property, we give a tester with query complexity d·poly(ε^-1). The previous line of work on (independent of n, 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.
READ FULL TEXT