## 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_{0} and a degree function δ:V→N_{0}, together with three integers k_{v}, k_{e} and C. The question is whether we can delete a set of vertices of total weight at most k_{v} and a set of edges of total weight at most k_{e} 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 k_{v}+k_{e}. We prove that, when restricted to planar graphs, they stay NP-complete but have polynomial kernels when parameterized by k_{v}+k_{e}.

Original language | English |
---|---|

Pages (from-to) | 168-182 |

Number of pages | 15 |

Journal | Journal of computer and system sciences |

Volume | 85 |

DOIs | |

Publication status | Published - 1 May 2017 |

Externally published | Yes |

## Keywords

- Connected graph
- Graph editing
- Planar graph
- Polynomial kernel