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→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[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. (2015). Editing to a planar graph of given degrees. In Computer science - theory and applications : 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, proceedings (143-156). https://doi.org/10.1007/978-3-319-20297-6_10
Publication Date | Jun 23, 2015 |
---|---|
Deposit Date | Aug 12, 2015 |
Publicly Available Date | Jun 23, 2016 |
Pages | 143-156 |
Series Title | Lecture notes in computer science |
Series Number | 9139 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Computer science - theory and applications : 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, proceedings. |
ISBN | 9783319202969 |
DOI | https://doi.org/10.1007/978-3-319-20297-6_10 |
Public URL | https://durham-repository.worktribe.com/output/1152770 |
Files
Accepted Conference Proceeding
(347 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-20297-6_10
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