Editing to a planar graph of given degrees

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

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationComputer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings
EditorsLev D. Beklemishev, Daniil V. Musatov, Daniil V. Musatov
PublisherSpringer Verlag
Pages143-156
Number of pages14
ISBN (Print)9783319202969
DOIs
StatePublished - 2015
Event10th International Computer Science Symposium in Russia, CSR 2015 - Listvyanka, Russian Federation
Duration: Jul 13 2015Jul 17 2015

Publication series

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

Conference

Conference10th International Computer Science Symposium in Russia, CSR 2015
Country/TerritoryRussian Federation
CityListvyanka
Period7/13/157/17/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

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

Cite this