Linear kernels and single-exponential algorithms via protrusion decompositions

2012/10/19 Fri 4PM-5PM

A *t-treewidth-modulator* of a graph G is a set X⊆V(G) such that the treewidth of G-X is at most some constant t-1. In this paper, we present a novel algorithm to compute a decomposition scheme for graphs G that come equipped with a t-treewidth-modulator. This decomposition, called a *protrusion decomposition*, is the cornerstone in obtaining the following two main results.

We first show that any parameterized graph problem (with parameter k) that has *finite integer index* and is *treewidth-bounding* admits a linear kernel on H-topological-minor-free graphs, where H is some arbitrary but fixed graph. A parameterized graph problem is called treewidth-bounding if all positive instances have a t-treewidth-modulator of size O(k), for some constant t. This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus [Bodlaender et al., FOCS 2009] and H-minor-free graphs [Fomin et al., SODA 2010].

Our second application concerns the Planar-F-Deletion problem. Let F be a fixed finite family of graphs containing at least one planar graph. Given an n-vertex graph G and a non-negative integer k, Planar-F-Deletion asks whether G has a set X⊆ V(G) such that |X|≤k and G-X is H-minor-free for every H∈F. Very recently, an algorithm for Planar-F-Deletion with running time 2^{O(k)} n log^{2} n (such an algorithm is called *single-exponential*) has been presented in [Fomin et al., FOCS 2012] under the condition that every graph in F is connected. Using our algorithm to construct protrusion decompositions as a building block, we get rid of this connectivity constraint and present an algorithm for the general Planar-F-Deletion problem running in time 2^{O(k)}n^{2}.

This is a joint work with Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar.