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).
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-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)
|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
|Look up in GoogleScholar|