Akash Kumar : Finding minors in sublinear time in bounded-degree graphs with (almost) optimal one-sided query complexity

Posted by Will Perkins , part of the Computer Science Theory Seminar.

At

Sept. 25, 2019, 4:15 p.m.

In

1325 SEO

Abstract

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. 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). (Joint work with C. Seshadhri and Andrew Stolman)