Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints

Belmonte, R.; Golovach, P.A.; Hof, van 't P.; Paulusma, D.

Abstract

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).

Citation

Belmonte, R., Golovach, P., Hof, V. '. P., & Paulusma, D. (2013, December). Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints. Presented at 8th International Symposium, IPEC 2013, Sophia Antipolis, France

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 8th International Symposium, IPEC 2013
• Publication Date: Jan 1, 2013
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 15, 2015
• Print ISSN: 0302-9743
• Pages: 16-27
• Series Title: Lecture notes in computer science
• Series Number: 8246
• Series ISSN: 0302-9743,1611-3349
• Book Title: 8th International Symposium, IPEC 2013, 4-6 September 2013, Sophia Antipolis, France ; revised selected papers.
• DOI: https://doi.org/10.1007/978-3-319-03898-8_3
• Public URL: https://durham-repository.worktribe.com/output/1153201