Editing to a planar graph of given degrees

Konrad Kazimierz 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 Kazimierz Dabrowski, Petr A. Golovach, Pim van 't Hof, Daniël Paulusma, Dimitrios M. Thilikos

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

4 Citations (Scopus)

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

Original language	English
Title of host publication	Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, Proceedings
Editors	Lev D. Beklemishev, Daniil V. Musatov
Publisher	Springer
Pages	143-156
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-319-20297-6_10
Publication status	Published - 2015
Event	10th International Computer Science Symposium in Russia, CSR 2015 - hotel Krestovaya Pad, Listvyanka, Russian Federation Duration: 13 Jul 2015 → 17 Jul 2015 Conference number: 10

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9139

Conference

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

Access to Document

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

10.1007_978-3-319-20297-6_10Accepted author version, 446 KB

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 (Eds.), 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; Vol. 9139). Springer. https://doi.org/10.1007/978-3-319-20297-6_10

Dabrowski, Konrad Kazimierz ; 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, Listvyanka, Russia, July 13-17, 2015, Proceedings. editor / Lev D. Beklemishev ; Daniil V. Musatov. Springer, 2015. pp. 143-156 (Lecture Notes in Computer Science).

@inproceedings{1ce47b831d014eb39716f45d08bedca8,

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

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

year = "2015",

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

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "143--156",

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

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

address = "Germany",

note = "10th International Computer Science Symposium in Russia, CSR 2015, CSR 2015 ; Conference date: 13-07-2015 Through 17-07-2015",

}

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 (eds), Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, Proceedings. Lecture Notes in Computer Science, vol. 9139, Springer, pp. 143-156, 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russian Federation, 13/07/15. https://doi.org/10.1007/978-3-319-20297-6_10

Editing to a planar graph of given degrees. / Dabrowski, Konrad Kazimierz; Golovach, Petr A.; van 't Hof, Pim et al.
Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, Proceedings. ed. / Lev D. Beklemishev; Daniil V. Musatov. Springer, 2015. p. 143-156 (Lecture Notes in Computer Science; Vol. 9139).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Editing to a planar graph of given degrees

AU - Dabrowski, Konrad Kazimierz

AU - Golovach, Petr A.

AU - van 't Hof, Pim

AU - Paulusma, Daniël

AU - Thilikos, Dimitrios M.

N1 - Conference code: 10

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

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

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

M3 - Conference contribution

T3 - Lecture Notes in Computer Science

SP - 143

EP - 156

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

A2 - Beklemishev, Lev D.

A2 - Musatov, Daniil V.

PB - Springer

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

Y2 - 13 July 2015 through 17 July 2015

ER -

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, editors, Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, Proceedings. Springer. 2015. p. 143-156. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-20297-6_10

Editing to a planar graph of given degrees

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this