Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H , and suppose one must remove n edges from G to make it H -minor free (for some small constant 0"> 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 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 prior sublinear time bound was known for this problem.

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 ( n ) lower bound of Czumaj et al (RSA 2014).

Prior to this work, the only graphs H for which non-trivial one-sided 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 2 ) -grid, and the k -circus (Fichtenberger et al, Arxiv 2017).