Editing to a planar graph of given degreesKonrad K. Dabrovski, Petr A. Golovach, Pim van 't Hof, Daniël Paulusma and Dimitrios M. Thilikos
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.
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 → ℕ0, together with three integers kv, ke and C. The question is whether we can delete a set of vertices of total weight at most kv and a set of edges of total weight at most ke 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-hard when parameterized by kv + ke. We prove that, when restricted to planar graphs, they stay NP-complete but have polynomial kernels when parameterized by kv + ke.