Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions

DOI10.1145/2797140zbMATH Open1398.68245arXiv1207.0835OpenAlexW1838629830MaRDI QIDQ4962217

Author name not available (Why is that?)

Publication date: 30 October 2018

Published in: (Search for Journal in Brave)

Abstract: A emph{$t$-treewidth-modulator} of a graph $G$ is a set $XsubseteqV(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 emph{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 emph{finite integer index} and is emph{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-$mathcalF$-Deletion problem. Let $mathcalF$ 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-$mathcalF$-Deletion asks whether $G$ has a set $XsubseteqV(G)$ such that $|X|leqk$ and $G-X$ is $H$-minor-free for every $HinmathcalF$. Very recently, an algorithm for Planar-$mathcalF$-Deletion with running time $2^{O(k)}nlo{g}^{2}n$ (such an algorithm is called emph{single-exponential}) has been presented in [Fomin et al., FOCS 2012] under the condition that every graph in $mathcalF$ 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-$mathcalF$-Deletion problem running in time $2^{O(k)}{n}^2$.

Full work available at URL: https://arxiv.org/abs/1207.0835

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962217)