Department of
Applied
Mathematics

Subexponential Parameterized Algorithms for Planar Graphs, Apex-Minor-Free Graphs and Graphs of Polynomial Growth via Low Treewidth Pattern Covering

Marcin Pilipczuk

Abstract

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties:

* A induces a subgraph of G of treewidth O(sqrt(k) log(k)), and * for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least the inverse of (2^{O(sqrt(k) log^2(k))}n^{O(1)}), where n is the number of vertices of G.

Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound 2^{O(sqrt(k) log^2(k))} n^{O(1)}. The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph; examples of such problems include Directed k-Path, Weighted k-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface. We also provide a similar statement for graph classes of polynomial growth.

In the talk I will first focus on the background and motivation, and then highlight the main ideas of the proof by sketching the proof for the case of graph classes of polynomial growth. Based on joint work with Fedor Fomin, Daniel Lokshtanov, Daniel Marx, Micha³ Pilipczuk, and Saket Saurabh: http://arxiv.org/abs/1604.05999 and http://arxiv.org/abs/1610.07778