Linear Kernels and Single-exponential Algorithms via Protrusion Decompositions

Abstract : We present a linear-time algorithm to compute a decomposition scheme for graphs $G$ that have a set $X \subseteq V(G)$, called a \emph{treewidth-modulator}, such that the treewidth of $G-X$ is bounded by a constant. Our decomposition, called a \emph{protrusion decomposition}, is the cornerstone in obtaining the following two main results. Our first result is that any parameterized graph problem (with parameter $k$) that has \emph{finite integer index} and such that positive instances have a treewidth-modulator of size $O(k)$ admits a linear kernel on the class of $H$-topological-minor-free graphs, for any fixed graph $H$. This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus and $H$-minor-free graphs. Let $\mathcal{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$, \planarF{} asks whether $G$ has a set $X\subseteq V(G)$ such that $|X|\leqslant k$ and $G-X$ is $H$-minor-free for every $H\in \mc{F}$. As our second application, we present the first \emph{single-exponential} algorithm to solve \planarF{}. Namely, our algorithm runs in time $2^{O(k)}\cdot n^2$, which is asymptotically optimal with respect to~$k$. So far, single-exponential algorithms were only known for special cases of the family $\mathcal{F}$.
Document type :
Conference papers
Complete list of metadatas
Contributor : Christophe Paul <>
Submitted on : Tuesday, June 4, 2013 - 11:22:17 AM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM

Links full text



Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, et al.. Linear Kernels and Single-exponential Algorithms via Protrusion Decompositions. ICALP: International Colloquium on Automata, Languages and Programming, Jul 2013, Riga, Latvia. pp.613-624, ⟨10.1007/978-3-642-39206-1_52⟩. ⟨lirmm-00829999⟩



Record views