TY - JOUR

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 - Funding Information:
An extended abstract of this paper appeared in the proceedings of CSR 2015 [10]. The first and fourth authors were supported by EPSRC Grant EP/K025090/1. The research of the second author received funding from the European Research Council under the European Union's Seventh Framework Programme (FP/2007–2013)/ERC Grant Agreement n. 267959. The research of the fifth author was co-financed by the European Union (European Social Fund ESF) and Greek national funds through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF) – Research Funding Program: ARISTEIA II.
Publisher Copyright:
© 2016 The Authors

PY - 2017/5/1

Y1 - 2017/5/1

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

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

KW - Connected graph

KW - Graph editing

KW - Planar graph

KW - Polynomial kernel

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

U2 - 10.1016/j.jcss.2016.11.009

DO - 10.1016/j.jcss.2016.11.009

M3 - Article

AN - SCOPUS:85006365103

SN - 0022-0000

VL - 85

SP - 168

EP - 182

JO - Journal of computer and system sciences

JF - Journal of computer and system sciences

ER -