Contracting graphs to paths and trees

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

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

33 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 a tree or a path, respectively, by a sequence of at most k edge contractions in G. For TREE CONTRACTION, we present a randomized 4k  n O(1) time polynomial-space algorithm, as well as a deterministic 4.98k  n O(1) time algorithm, based on a variant of the color coding technique of Alon, Yuster and Zwick. We also present a deterministic 2k+o(k)+n O(1) time algorithm 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
Pages (from-to)109-132
Number of pages24
JournalAlgorithmica
Volume68
Issue number1
Early online date26 Jun 2012
DOIs
Publication statusE-pub ahead of print/First online - 26 Jun 2012
Externally publishedYes

Cite this