Editing to a planar graph of given degrees
Konrad K. Dabrowski, Petr A. Golovach, Pim van ’t Hof, Daniël Paulusma, Dimitrios M. Thilikos · Journal of Computer and System Sciences · 2016
We consider the following graph modification problem. Let the input consist of a graph G = ( V , E ) , a weight function w : V ∪ E → N , a cost function c : V ∪ E → N 0 and a degree function δ : V → 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 δ ( 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 .