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.1007/978-3-319-20297-6_10

Editing to a planar graph of given degrees

Konrad K. Dabrowski, Petr A. Golovach, Pim van’T Hof, Daniël Paulusma, Dimitrios M. Thilikos

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

Original language	English (US)
Title of host publication	Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings
Editors	Lev D. Beklemishev, Daniil V. Musatov, Daniil V. Musatov
Publisher	Springer Verlag
Pages	143-156
Number of pages	14
ISBN (Print)	9783319202969
DOIs	https://doi.org/10.1007/978-3-319-20297-6_10
State	Published - 2015
Event	10th International Computer Science Symposium in Russia, CSR 2015 - Listvyanka, Russian Federation Duration: Jul 13 2015 → Jul 17 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9139
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Computer Science Symposium in Russia, CSR 2015
Country/Territory	Russian Federation
City	Listvyanka
Period	7/13/15 → 7/17/15

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Dabrowski, K. K., Golovach, P. A., van’T Hof, P., Paulusma, D., & Thilikos, D. M. (2015). Editing to a planar graph of given degrees. In L. D. Beklemishev, D. V. Musatov, & D. V. Musatov (Eds.), Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings (pp. 143-156). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9139). Springer Verlag. https://doi.org/10.1007/978-3-319-20297-6_10

Editing to a planar graph of given degrees. / Dabrowski, Konrad K.; Golovach, Petr A.; van’T Hof, Pim et al.
Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings. ed. / Lev D. Beklemishev; Daniil V. Musatov; Daniil V. Musatov. Springer Verlag, 2015. p. 143-156 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9139).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Dabrowski, KK, Golovach, PA, van’T Hof, P, Paulusma, D & Thilikos, DM 2015, Editing to a planar graph of given degrees. in LD Beklemishev, DV Musatov & DV Musatov (eds), Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9139, Springer Verlag, pp. 143-156, 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russian Federation, 7/13/15. https://doi.org/10.1007/978-3-319-20297-6_10

Dabrowski KK, Golovach PA, van’T Hof P, Paulusma D, Thilikos DM. Editing to a planar graph of given degrees. In Beklemishev LD, Musatov DV, Musatov DV, editors, Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings. Springer Verlag. 2015. p. 143-156. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-20297-6_10

Dabrowski, Konrad K. ; Golovach, Petr A. ; van’T Hof, Pim et al. / Editing to a planar graph of given degrees. Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings. editor / Lev D. Beklemishev ; Daniil V. Musatov ; Daniil V. Musatov. Springer Verlag, 2015. pp. 143-156 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{36cf74574b8f48e9b13d569601edec13,

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 → 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 {\textquoteleft}. We also consider the variant in which G {\textquoteleft} 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.",

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

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 10th International Computer Science Symposium in Russia, CSR 2015 ; Conference date: 13-07-2015 Through 17-07-2015",

year = "2015",

doi = "10.1007/978-3-319-20297-6_10",

language = "English (US)",

isbn = "9783319202969",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "143--156",

editor = "Beklemishev, {Lev D.} and Musatov, {Daniil V.} and Musatov, {Daniil V.}",

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

}

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.

PB - Springer Verlag

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

Y2 - 13 July 2015 through 17 July 2015

ER -

Editing to a planar graph of given degrees

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this