Show simple item record

Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKim, Eun Jung*
hal.structure.identifierDepartment of Computer Science [Aachen]
dc.contributor.authorLanger, Alexander*
hal.structure.identifierLaboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
dc.contributor.authorPaul, Christophe
HAL ID: 4726		*
hal.structure.identifierDepartment of Computer Science [Aachen]
dc.contributor.authorReidl, Felix*
hal.structure.identifierDepartment of Computer Science [Aachen]
dc.contributor.authorRossmanith, Peter*
hal.structure.identifierLaboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
dc.contributor.authorSau Valls, Ignasi
HAL ID: 7331
ORCID: 0000-0002-8981-9287		*
hal.structure.identifierDepartment of Computer Science [Aachen]
dc.contributor.authorSikdar, Somnath*
dc.date.accessioned2016-10-19T09:10:23Z
dc.date.available2016-10-19T09:10:23Z
dc.date.issued2013-07
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/15885
dc.language.isoenen
dc.subjectparameterized complexityen
dc.subjectlinear kernelsen
dc.subjectalgorithmic meta-theoremsen
dc.subjectsparse graphsen
dc.subjectsingle-exponential algorithmsen
dc.subjectgraph minorsen
dc.subject.ddc511en
dc.subject.classificationjelC.C6.C65en
dc.titleLinear Kernels and Single-Exponential Algorithms via Protrusion Decompositionsen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.en
dc.identifier.citationpages613-624en
dc.relation.ispartoftitleAutomata, Languages, and Programming. 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part Ien
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2013
dc.relation.ispartofpages853en
dc.relation.ispartofurl10.1007/978-3-642-39206-1en
dc.identifier.urlsitehttps://arxiv.org/abs/1207.0835v2en
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.ispartofisbn978-3-642-39205-4en
dc.relation.conftitleAutomata, Languages, and Programming. 40th International Colloquium, ICALP 2013en
dc.relation.confdate2013-07
dc.relation.confcityRigaen
dc.relation.confcountryLatviaen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-642-39206-1_52en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2016-07-06T15:08:43Z
hal.identifierhal-01383776*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record