Pim van 't Hof

Contracting graphs to paths and trees

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

Algorithmica, vol. 68, no. 1, pp. 109-132, 2014.
[DOI][Preprint]

A preliminary version of this paper appeared in the proceedings of IPEC 2011, the 6th International Symposium on Parameterized and Exact Computation (held on September 7-9, 2011 in Saarbrücken, Germany), Lecture Notes in Computer Science, vol. 7112, pp. 55-66, 2012.
[DOI][Slides]

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. Interestingly, 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, which we call Tree Contraction and Path Contraction. These two problems take as input an undirected graph G 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. Our main contribution is 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 strong connection between Tree Contraction and Feedback Vertex Set, which is known to have a vertex kernel with size O(k²).