## 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* → ℕ_{0}, together with three integers *k _{v}*,

*k*and

_{e}*C*. The question is whether we can delete a set of vertices of total weight at most

*k*and a set of edges of total weight at most

_{v}*k*so that the total cost of the deleted elements is at most

_{e}*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*. We prove that, when restricted to planar graphs, they stay NP-complete but have polynomial kernels when parameterized by

_{e}*k*+

_{v}*k*.

_{e}