TCS+ Talk

Wednesday October 17, 2018 10:00 AM

Finding forbidden minors through random walks: (almost) n^{1/2} query one-sided testers for minor closed properties

Speaker: C. Seshadri, UC Santa Cruz
Location: Annenberg 322

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


Series TCS+ Talks

Contact: Bonnie Leung