Pim van 't Hof

Editing to a planar graph of given degrees

Konrad K. Dabrovski, Petr A. Golovach, Pim van 't Hof, Daniël Paulusma and Dimitrios M. Thilikos

Journal of Computer and System Sciences, vol. 85, pp. 168-182, 2017.
[DOI] [arXiv]

A preliminary version of this paper will appear in the proceedings of CSR 2015, the 10th International Computer Science Symposium in Russia (to be held on July 13-17, 2015 in Listvyanka, Russia).
Lecture Notes in Computer Science, vol. 9139, pp. 143-156, 2015.
[DOI]

Abstract:

We consider the following graph modification problem. Let the input consist of a graph G=(V,E), a weight function w : V ∪ E → ℕ, a cost function c : V ∪ E → ℕ and a degree function δ : V → ℕ₀, together with three integers k_v, k_e and C. The question is whether we can delete a set of vertices of total weight at most k_v and a set of edges of total weight at most k_e so that the total cost of the deleted elements is at most C and every non-deleted vertex v has degree δ(v) in the resulting graph G'. We also consider the variant in which G' must be connected. Both problems are known to be NP-complete and W[1]-hard when parameterized by k_v + k_e. We prove that, when restricted to planar graphs, they stay NP-complete but have polynomial kernels when parameterized by k_v + k_e.