Editing to a planar graph of given degrees

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
10 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 languageEnglish
Title of host publicationComputer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, Proceedings
EditorsLev D. Beklemishev, Daniil V. Musatov
PublisherSpringer Singapore
Pages143-156
Number of pages14
DOIs
Publication statusPublished - 2015
Event10th International Computer Science Symposium in Russia, CSR 2015 - hotel Krestovaya Pad, Listvyanka, Russian Federation
Duration: 13 Jul 201517 Jul 2015
Conference number: 10

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9139

Conference

Conference10th International Computer Science Symposium in Russia, CSR 2015
Abbreviated titleCSR 2015
CountryRussian Federation
CityListvyanka
Period13/07/1517/07/15

Fingerprint Dive into the research topics of 'Editing to a planar graph of given degrees'. Together they form a unique fingerprint.

Cite this