Skip to main content

Research Repository

Advanced Search

Editing to a Planar Graph of Given Degrees

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

Editing to a Planar Graph of Given Degrees Thumbnail


Authors

K.K. Dabrowski

P.A. Golovach

P. van 't Hof

D.M. Thilikos



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 Mar 28, 2024
Journal Journal of Computer and System Sciences
Print ISSN 0022-0000
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

Files

Accepted Journal Article (430 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
This article is available under the terms of the Creative Commons Attribution License (CC BY).
You may copy and distribute the article, create extracts, abstracts and new works from the article, alter and revise the article, text or data mine the article and otherwise reuse the article commercially (including reuse and/or resale of the article) without permission from Elsevier. You must give appropriate credit to the original work, together with a link to the formal publication through the relevant DOI and a link to the Creative Commons user license above. You must indicate if any changes are made but not in any way that suggests the licensor endorses you or your use of the work.






You might also like



Downloadable Citations