Parameterized complexity of three edge contraction problems with degree constraints
Rémy Belmonte, Petr A. Golovach, Pim van 't Hof and Daniël Paulusma
Acta Informatica, vol. 51, no. 7, pp. 473-497, 2014.
[DOI][Preprint]
A preliminary version of this paper, entitled "Parameterized complexity of two edge contraction problems with degree constraints", appeared in the proceedings of IPEC 2013, the 8th International Symposium on Parameterized and Exact Computation (held on September 4-6, 2013 in Sophia Antipolis, France), Lecture Notes in Computer Science, vol. 8246, pp. 16-27, 2013.
[DOI]
Abstract:
For any graph class ℌ, the ℌ-Contraction problem takes as input a graph G and an integer k, and asks whether there exists a graph H ∈ ℌ such that G can be modified into H using at most k edge contractions. We study the parameterized complexity of ℌ-Contraction for three different classes ℌ: the class ℌ≤d of graphs with maximum degree at most d, the class ℌ=d of d-regular graphs, and the class of d-degenerate graphs. We completely classify the parameterized complexity of all three problems with respect to the parameters k, d, and d+k. Moreover, we show that ℌ-Contraction admits an O(k) vertex kernel on connected graphs when ℌ ∈ {ℌ≤2,ℌ=2}, while the problem is W[2]-hard when ℌ is the class of 2-degenerate graphs and hence is expected not to admit a kernel at all. In particular, our results imply that ℌ-Contraction admits a linear vertex kernel when ℌ is the class of cycles.