Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions
Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau Valls, Ignasi; Sikdar, Somnath (2013-07), Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions, Automata, Languages, and Programming. 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, Springer : Berlin, p. 613-624. 10.1007/978-3-642-39206-1_52
Type
Communication / ConférenceExternal document link
https://arxiv.org/abs/1207.0835v2Date
2013-07Conference title
Automata, Languages, and Programming. 40th International Colloquium, ICALP 2013Conference date
2013-07Conference city
RigaConference country
LatviaBook title
Automata, Languages, and Programming. 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part IPublisher
Springer
Published in
Berlin
ISBN
978-3-642-39205-4
Number of pages
853Pages
613-624
Publication identifier
Metadata
Show full item recordAuthor(s)
Kim, Eun JungLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Langer, Alexander
Department of Computer Science [Aachen]
Paul, Christophe
Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
Reidl, Felix
Department of Computer Science [Aachen]
Rossmanith, Peter
Department of Computer Science [Aachen]
Sau Valls, Ignasi

Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
Sikdar, Somnath
Department of Computer Science [Aachen]
Abstract (EN)
We present a linear-time algorithm to compute a decomposition scheme for graphs G that have a set X ⊆ V(G), called a treewidth-modulator, such that the treewidth of G − X is bounded by a constant. Our decomposition, called a 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 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 Fbe 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. As our second application, we present the first single-exponential algorithm to solve Planar F- Deletion. Namely, our algorithm runs in time 2 O(k)·n 2, which is asymptotically optimal with respect to k. So far, single-exponential algorithms were only known for special cases of the family F.Subjects / Keywords
parameterized complexity; linear kernels; algorithmic meta-theorems; sparse graphs; single-exponential algorithms; graph minorsRelated items
Showing items related by title and author.
-
Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau Valls, Ignasi (2016) Article accepté pour publication ou publié
-
Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017) Article accepté pour publication ou publié
-
Kim, Eun Jung; Oum, Sang-il; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2018) Article accepté pour publication ou publié
-
Kim, Eun Jung; Oum, Sang-Il; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2015) Communication / Conférence
-
Cohen, Nathann; Gonçalves, Daniel; Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017) Article accepté pour publication ou publié