## 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.