Contracting graphs to paths and trees

Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque, Daniel Lokshtanov, Christophe Paul

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

11 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationParameterized and Exact Computation - 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers
EditorsDániel Marx, Peter Rossmanith
PublisherSpringer Singapore
Pages55-66
Number of pages12
ISBN (Electronic)978-3-642-28050-4
ISBN (Print)978-3-642-28049-8
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event6th International Symposium on Parameterized and Exact Computation, IPEC 2011 - Saarbrücken, Germany
Duration: 6 Sep 20118 Sep 2011
Conference number: 6

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume7112

Conference

Conference6th International Symposium on Parameterized and Exact Computation, IPEC 2011
Abbreviated titleIPEC
CountryGermany
CitySaarbrücken
Period6/09/118/09/11

Fingerprint

Dive into the research topics of 'Contracting graphs to paths and trees'. Together they form a unique fingerprint.

Cite this