Editing to a Planar Graph of Given Degrees

Dabrowski, K.K.; Golovach, P.A.; van 't Hof, P.; Paulusma, D.; Thilikos, D.M.

Abstract

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→N0 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[1]-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.

Citation

Dabrowski, K., Golovach, P., van 't Hof, P., Paulusma, D., & Thilikos, D. (2016). Editing to a Planar Graph of Given Degrees. Journal of Computer and System Sciences, 85, 168-182. https://doi.org/10.1016/j.jcss.2016.11.009

• Journal Article Type: Article
• Acceptance Date: Nov 26, 2016
• Online Publication Date: Dec 1, 2016
• Publication Date: Dec 1, 2016
• Deposit Date: Dec 1, 2016
• Publicly Available Date: Dec 2, 2016
• Journal: Journal of Computer and System Sciences
• Print ISSN: 0022-0000
• Electronic ISSN: 1090-2724
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 85
• Pages: 168-182
• DOI: https://doi.org/10.1016/j.jcss.2016.11.009
• Public URL: https://durham-repository.worktribe.com/output/1368859