Contracting Graphs to Paths and Trees

Pinar Heggerness 1 Pim Van'T Hof 1 Benjamin Lévêque 2 Daniel Lokshtanov 1 Christophe Paul 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Vertex deletion and edge deletion problems play a central role in Parameterized Complexity. Examples include classical problems like Feedback Vertex Set, Odd Cycle Transversal, and Chordal Deletion. The study of analogous edge contraction problems has so far been left largely unexplored from a parameterized perspective. We consider two basic problems of this type: Tree Contraction and Path Contraction. These two problems take as input an undirected graph G on n vertices and an integer k, and the task is to determine whether we can obtain an acyclic graph or a path, respectively, by a sequence of at most k edge contractions in G. We present an algorithm with running time $4.98^k n^{O(1)}$ for Tree Contraction, based on a variant of the color coding technique of Alon, Yuster and Zwick, and an algorithm with running time $2 ^{k + o(k)} + n^{O(1)}$ for Path Contraction. Furthermore, we show that Path Contraction has a kernel with at most $5k + 3$ vertices, while Tree Contraction does not have a polynomial kernel unless NP ⊆ coNP/poly. We find the latter result surprising, because of the connection between Tree Contraction and Feedback Vertex Set, which is known to have a kernel with $4k^2$ vertices.
Type de document :
Communication dans un congrès
IPEC: International Symposium on Parameterized and Exact Computation, Sep 2011, Saarbrücken, Germany. pp.55-66, 2011, LNCS
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00805183
Contributeur : Christophe Paul <>
Soumis le : mercredi 27 mars 2013 - 12:24:09
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-00805183, version 1

Collections

Citation

Pinar Heggerness, Pim Van'T Hof, Benjamin Lévêque, Daniel Lokshtanov, Christophe Paul. Contracting Graphs to Paths and Trees. IPEC: International Symposium on Parameterized and Exact Computation, Sep 2011, Saarbrücken, Germany. pp.55-66, 2011, LNCS. 〈lirmm-00805183〉

Partager

Métriques

Consultations de la notice

117