Linear Kernels and Single-exponential Algorithms via Protrusion Decompositions - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2013

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}$.

Dates and versions

lirmm-00829999 , version 1 (04-06-2013)

Identifiers

Cite

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⟩
420 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More