Editing to a Planar Graph of Given Degrees

5 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We consider the following graph modification problem. Let the input consist of a graph $G=(V,E)$, a weight function $w\colon V\cup E\rightarrow \mathbb{N}$, a cost function $c\colon V\cup E\rightarrow \mathbb{N}$ and a degree function $\delta\colon V\rightarrow \mathbb{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 $\delta(v)$ in the resulting graph~$G'$. We also consider the variant in which ~$G'$ must be connected. Both problems are known to be \classNP-complete and \classW{1}-hard when parameterized by $k_v+k_e$. We prove that, when restricted to planar graphs, they stay \classNP-complete but have polynomial kernels when parameterized by $k_v+k_e$.
Type de document :
Communication dans un congrès
CSR: Computer Science Symposium in Russia, Jul 2015, Listvyanka, Russia. Springer, 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, Proceedings, LNCS (9139), pp.143-156, 2015, Computer Science -- Theory and Applications. 〈10.1007/978-3-319-20297-6_10〉
Domaine :

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01225602
Contributeur : Dimitrios M. Thilikos <>
Soumis le : vendredi 6 novembre 2015 - 13:23:10
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Citation

Konrad K. Dabrowski, Petr A. Golovach, Pim Van'T Hof, Daniël Paulusma, Dimitrios M. Thilikos. Editing to a Planar Graph of Given Degrees. CSR: Computer Science Symposium in Russia, Jul 2015, Listvyanka, Russia. Springer, 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, Proceedings, LNCS (9139), pp.143-156, 2015, Computer Science -- Theory and Applications. 〈10.1007/978-3-319-20297-6_10〉. 〈lirmm-01225602〉

Métriques

Consultations de la notice