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: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)168-182
Number of pages15
JournalJournal of Computer and System Sciences
Volume85
DOIs
StatePublished - May 1 2017

Keywords

  • Connected graph
  • Graph editing
  • Planar graph
  • Polynomial kernel

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

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

Cite this