skip to main content

TCS+ Talk

Wednesday, October 17, 2018
10:00am to 11:00am
Add to Cal
Annenberg 322
Finding forbidden minors through random walks: (almost) n^{1/2} query one-sided testers for minor closed properties
C. Seshadri, UC Santa Cruz,

Abstract:  Let G be an undirected, bounded degree graph with n vertices.  Fix a finite graph H, and suppose one must remove eps*n edges from G to make it H-minor free (for some small constant eps > 0). We give a nearly n^{1/2} time algorithm that, with high probability, finds an H-minor in such a graph.

As an application, consider a graph G that requires eps*n edge removals 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 result 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 lower bounds of Czumaj et al (RSA 2014).

Joint work with Akash Kumar and Andrew Stolman


For more information, please contact Bonnie Leung by email at [email protected].