Linear kernels and single-exponential algorithms via protrusion decompositions

Eun Jung Kim (김은정)

CNRS, LAMSADE, Paris, France.

CNRS, LAMSADE, Paris, France.

2012/10/19 Fri 4PM-5PM

A

We first show that any parameterized graph problem (with parameter k) that has

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

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

*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.

Tags: 김은정