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 language | English (US) |
---|---|
Pages (from-to) | 168-182 |
Number of pages | 15 |
Journal | Journal of Computer and System Sciences |
Volume | 85 |
DOIs | |
State | Published - 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