Polynomial Kernels for 3-Leaf Power Graph Modification Problems

Abstract : A graph G = (V,E) is a 3-leaf power iff there exists a tree T the leaf set of which is V and such that (u,v) belong to E iff u and v are at distance at most 3 in T. The 3-leaf power graph edge modification problems, i.e. edition (also known as the Closest 3-Leaf Power), completion and edge-deletion are FPT when parameterized by the size of the edge set modification. However, polynomial kernels were known for none of these three problems. For each of them, we provide kernels with O(k^3) vertices that can be computed in linear time. We thereby answer an open problem first mentioned by Dom, Guo, Hüffner and Niedermeier.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2010, 158 (16), pp.1732-1744
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00533517
Contributeur : Christophe Paul <>
Soumis le : dimanche 7 novembre 2010 - 07:56:15
Dernière modification le : jeudi 19 juillet 2018 - 11:54:04

Identifiants

  • HAL Id : lirmm-00533517, version 1

Collections

Citation

Stéphane Bessy, Christophe Paul, Anthony Perez. Polynomial Kernels for 3-Leaf Power Graph Modification Problems. Discrete Applied Mathematics, Elsevier, 2010, 158 (16), pp.1732-1744. 〈lirmm-00533517〉

Partager

Métriques

Consultations de la notice

119