• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions

Thumbnail
Date
2013-07
Link to item file
https://arxiv.org/abs/1207.0835v2
Dewey
Principes généraux des mathématiques
Sujet
parameterized complexity; linear kernels; algorithmic meta-theorems; sparse graphs; single-exponential algorithms; graph minors
JEL code
C.C6.C65
DOI
http://dx.doi.org/10.1007/978-3-642-39206-1_52
Conference name
Automata, Languages, and Programming. 40th International Colloquium, ICALP 2013
Conference date
07-2013
Conference city
Riga
Conference country
Latvia
Book title
Automata, Languages, and Programming. 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I
Publisher
Springer
Publisher city
Berlin
Year
2013
Pages number
853
ISBN
978-3-642-39205-4
Book URL
10.1007/978-3-642-39206-1
URI
https://basepub.dauphine.fr/handle/123456789/15885
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Kim, Eun Jung
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Langer, Alexander
109169 Department of Computer Science [Aachen]
Paul, Christophe
181 Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
Reidl, Felix
109169 Department of Computer Science [Aachen]
Rossmanith, Peter
109169 Department of Computer Science [Aachen]
Sau Valls, Ignasi
181 Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
Sikdar, Somnath
109169 Department of Computer Science [Aachen]
Type
Communication / Conférence
Item number of pages
613-624
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.