Dabrowski, K.K. and Golovach, P.A. and van 't Hof, P. and Paulusma, D. and Thilikos, D.M. (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. , pp. 143-156. Lecture notes in computer science. (9139).
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.
| Item Type: | Book chapter |
|---|---|
| Full text: | (AM) Accepted Manuscript Download PDF (339Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | http://dx.doi.org/10.1007/978-3-319-20297-6_10 |
| Publisher statement: | The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-20297-6_10 |
| Date accepted: | No date available |
| Date deposited: | 21 August 2015 |
| Date of first online publication: | June 2015 |
| Date first made open access: | 23 June 2016 |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
