Finding forbidden minors in sublinear time: a $n^{1/2+o(1)}$-query one-sided tester for minor closed properties on bounded degree graphs

Understand

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.