ECCC-Report TR18-101https://eccc.weizmann.ac.il/report/2018/101Comments and Revisions published for TR18-101en-usMon, 21 May 2018 11:18:56 +0300
Paper TR18-101
| Finding forbidden minors in sublinear time: a $O(n^{1/2+o(1)})$-query one-sided tester for minor closed properties on bounded degree graphs |
Akash Kumar,
C. Seshadhri,
Andrew Stolman
https://eccc.weizmann.ac.il/report/2018/101Let $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. For an example 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 sublinear time bound was known for this problem, prior to this result.
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-Shapira (STOC 2008) 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 (RSA 2014).
Prior to this work, the only graphs $H$ for which non-trivial property testers were known for $H$-minor freeness are the following: $H$ being a forest or a cycle (Czumaj et al, RSA 2014), $K_{2,k}$, $(k\times 2)$-grid, and the $k$-circus (Fichtenberger et al, Arxiv 2017).Mon, 21 May 2018 11:18:56 +0300https://eccc.weizmann.ac.il/report/2018/101