Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
Akash S. Kumar, Comandur Seshadhri, Andrew Stolman · SIAM Journal on Computing · 2020
Let $G$ be an undirected, bounded degree graph with $n$ vertices. Fix a finite graph $H$, and suppose one must remove $\varepsilon n$ edges from $G$ to make it $H$-minor-free (for some small constant $\varepsilon > 0$). We give an $n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an $H$-minor in such a graph. As an application, suppose one must remove $\varepsilon n$ edges from a bounded degree graph $G$ to make it planar. This result implies an algorithm, with the same running time, that produces a $K_{3,3}$- or $K_5$-minor in $G$. No prior sublinear time bound was known for this problem. By the graph minor theorem, we get an analogous result for any minor-closed property. Up to $n^{o(1)}$ factors, this resolves a conjecture of Benjamini, Schramm, and Shapira [ Adv. Math., 223 (2010), pp. 2200--2218] on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal by an $\Omega(\sqrt{n})$ lower bound of Czumaj et al. [ Random Structures Algorithms, 45 (2014), pp. 139--184]. Prior to this work, the only graphs $H$ for which nontrivial one-sided property testers were known for $H$-minor-freeness were the following: $H$ being a forest or a cycle [Czumaj et al., Random Structures Algorithms, 45 (2014), pp. 139--184], $K_{2,k}$, $(k\times 2)$-grid, and the $k$-circus [Fichtenberger et al., preprint, arXiv:1707.06126v1, 2017].