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→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





You might also like



Downloadable Citations