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

by Akash Kumar, C. Seshadhri, and Andrew Stolman

Oded's comments

Needless to say, I value this result - having tried to obtain it several years ago.

As mentioned in this paper and elaborated in Sec 1.2 of CGRSSS, finding abundant substructures in graphs and one-sided error testing of the related property (i.e., lacking such substructures) are intimately related. Indeed, this relation is most appealing in the case of minor-free properties.

The initial idea outlined in the first paragraph of Sec 2.1 is very natural, but the problem is carrying it through in arbitrary graphs (rather than in the special case of rapid mixing). An indication to the difficulty involved is that even in the case that the forbidden minor is a 3-cycle, the analysis spans 18 pages of GR.

The original abstract

Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove $epsilon n$ edges from G to make it H-minor free (for some small positive constant epsilon). 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 $epsilon 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).

See ECCC TR18-101.

Back to list of Oded's choices.