Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints

Motivated by recent results of Mathieson and Szeider (J. Comput. Syst. Sci. 78(1): 179–191, 2012), we study two graph modification problems where the goal is to obtain a graph whose vertices satisfy certain degree constraints. The

Regular Contraction

problem takes as input a graph

G

and two integers

d

and

k

, and the task is to decide whether

G

can be modified into a

d

-regular graph using at most

k

edge contractions. The

Bounded Degree Contraction

problem is defined similarly, but here the objective is to modify

G

into a graph with maximum degree at most

d

. We observe that both problems are fixed-parameter tractable when parameterized jointly by

k

and

d

. We show that when only

k

is chosen as the parameter,

Regular Contraction

becomes

W

[1]-hard, while

Bounded Degree Contraction

becomes

W

[2]-hard even when restricted to split graphs. We also prove both problems to be

NP

-complete for any fixed

d

 ≥ 2. On the positive side, we show that the problem of deciding whether a graph can be modified into a cycle using at most

k

edge contractions, which is equivalent to

Regular Contraction

when

d

 = 2, admits an

O

(

k

) vertex kernel. This complements recent results stating that the same holds when the target is a path, but that the problem admits no polynomial kernel when the target is a tree, unless

NP

⊆ co

NP

/poly (Heggernes et al., IPEC 2011).