TY - GEN

T1 - Editing to a planar graph of given degrees

AU - Dabrowski, Konrad K.

AU - Golovach, Petr A.

AU - van’T Hof, Pim

AU - Paulusma, Daniël

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

N2 - 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 NPcomplete but have polynomial kernels when parameterized by kv + ke.

AB - 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 NPcomplete but have polynomial kernels when parameterized by kv + ke.

UR - http://www.scopus.com/inward/record.url?scp=84950108177&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84950108177&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-20297-6_10

DO - 10.1007/978-3-319-20297-6_10

M3 - Conference contribution

AN - SCOPUS:84950108177

SN - 9783319202969

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 143

EP - 156

BT - Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings

A2 - Beklemishev, Lev D.

A2 - Musatov, Daniil V.

A2 - Musatov, Daniil V.

PB - Springer Verlag

T2 - 10th International Computer Science Symposium in Russia, CSR 2015

Y2 - 13 July 2015 through 17 July 2015

ER -