Editing to a planar graph of given degrees

Konrad K. Dabrowski; Petr A. Golovach; Pim van 't Hof; Daniël Paulusma; Dimitrios M. Thilikos

doi:10.1016/j.jcss.2016.11.009

Editing to a planar graph of given degrees

Konrad K. Dabrowski^*
, Petr A. Golovach
, Pim van 't Hof
, Daniël Paulusma
, Dimitrios M. Thilikos

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

2 Citations (Scopus)

114 Downloads (Pure)

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→N₀, together with three integers k_v, k_e and C. The question is whether we can delete a set of vertices of total weight at most k_v and a set of edges of total weight at most k_e 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 k_v+k_e. We prove that, when restricted to planar graphs, they stay NP-complete but have polynomial kernels when parameterized by k_v+k_e.

Original language	English
Pages (from-to)	168-182
Number of pages	15
Journal	Journal of computer and system sciences
Volume	85
DOIs	https://doi.org/10.1016/j.jcss.2016.11.009
Publication status	Published - 1 May 2017
Externally published	Yes

Keywords

Connected graph
Graph editing
Planar graph
Polynomial kernel

Access to Document

10.1016/j.jcss.2016.11.009Licence: CC BY

ArticleFinal published version, 517 KBLicence: CC BY

Cite this

@article{67a8886f6f254377b93dd62d44f73b5d,

title = "Editing to a planar graph of given degrees",

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→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.",

keywords = "Connected graph, Graph editing, Planar graph, Polynomial kernel",

author = "Dabrowski, \{Konrad K.\} and Golovach, \{Petr A.\} and \{van 't Hof\}, Pim and Dani{\"e}l Paulusma and Thilikos, \{Dimitrios M.\}",

note = "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: {\textcopyright} 2016 The Authors",

year = "2017",

month = may,

day = "1",

doi = "10.1016/j.jcss.2016.11.009",

language = "English",

volume = "85",

pages = "168--182",

journal = "Journal of computer and system sciences",

issn = "0022-0000",

publisher = "Academic Press",

}

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 - https://www.scopus.com/pages/publications/85006365103

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 -

Editing to a planar graph of given degrees

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this