Editing to a Planar Graph of Given Degrees

Abstract

We consider the following graph modification problem. Let the input consist of a graph $G=(V,E)$, a weight function $w:V\cup E\to \mathbb{N}$, a cost function $c:V\cup E\to \mathbb{N}$ and a degree function $\delta :V\to {\mathbb{N}}_0$, 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 $\delta (v)$ in the resulting graph $G^{\prime }$. We also consider the variant in which $G^{\prime }$ 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$.