Wednesday, October 17, 2018
10:00 am

TCS+ talk

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


Contact Bonnie Leung
Add this event to my calendar