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}$.
Type de document :
Communication dans un congrès
ICALP: International Colloquium on Automata, Languages and Programming, Jul 2013, Riga, Latvia. 40th International Colloquium on Automata, Languages, and Programming, LNCS (7965), pp.613-624, 2013, 〈10.1007/978-3-642-39206-1_52〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00829999
Contributeur : Christophe Paul <>
Soumis le : mardi 4 juin 2013 - 11:22:17
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Citation

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. 40th International Colloquium on Automata, Languages, and Programming, LNCS (7965), pp.613-624, 2013, 〈10.1007/978-3-642-39206-1_52〉. 〈lirmm-00829999〉

Partager

Métriques

Consultations de la notice

162