Publication detailsDabrowski, K.K., Golovach, P.A., van 't Hof, P., Paulusma, D. & Thilikos, D.M. (2015), Editing to a planar graph of given degrees, Lecture Notes in Computer Science 9139: Springer, 143-156.
- Publication type: Conference Paper
- ISSN/ISBN: 0302-9743 (print), 1611-3349 (electronic), 9783319202969 (print), 9783319202976 (electronic)
- DOI: 10.1007/978-3-319-20297-6_10
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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 and a degree function δ:V→N0, 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.