K.K. Dabrowski
Editing to a Planar Graph of Given Degrees
Dabrowski, K.K.; Golovach, P.A.; van 't Hof, P.; Paulusma, D.; Thilikos, D.M.
Authors
P.A. Golovach
P. van 't Hof
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
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.
Published Journal Article
(529 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
You might also like
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Conference Proceeding
Disjunctive Temporal Problems under Structural Restrictions
(2021)
Conference Proceeding
Fine-Grained Complexity of Temporal Problems
(2020)
Conference Proceeding
Independent transversals versus transversals
(2019)
Conference Proceeding
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search