RANDOM WALKS AND FORBIDDEN MINORS II: A poly(dε-1)-QUERY TESTER FOR MINOR-CLOSED PROPERTIES OF BOUNDED-DEGREE GRAPHS.

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, and Shapira (Symposium on the Theory of Computing 2008) that gave a tester with query complexity triply exponential in ε - 1 . Levi and Ron [ACM Trans. Algorithms, 11 (2005), 24 2015] have given the best tester to date, with a quasi-polynomial (in ε - 1 ) query complexity. It remained an open problem to show whether there is a property tester 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 (Foundations of Computer Science 2018) analyzing random walk algorithms that find forbidden minors. [ABSTRACT FROM AUTHOR]