Contracting Graphs to Paths and Trees

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 5

k

 + 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 4

k

2

vertices.