We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Parameterized complexity of two edge contraction problems with degree constraints.

Belmonte, R. and Golovach, P.A. and Hof, van 't P. and Paulusma, D. (2013) 'Parameterized complexity of two edge contraction problems with degree constraints.', in 8th International Symposium, IPEC 2013, 4-6 September 2013, Sophia Antipolis, France ; revised selected papers. Berlin, Heidelberg: Springer, pp. 16-27. Lecture notes in computer science. (8246).


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 ⊆ coNP/poly (Heggernes et al., IPEC 2011).

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:No date available
Date deposited:15 January 2015
Date of first online publication:2013
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar