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)\in E$ iff $u$ and $v$ are at distance at most $3$ in $T$. The $3$-leaf power graph edge modification problems, \ie edition (also known as the \textsc{closest $3$-leaf power}), completion and edge-deletion are FPT when parameterized by the size of the edge set modification. However, a polynomial kernel was known for none of these three problems. For each of them, we provide a kernel 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~\cite{DGH05}.
Type de document :
Communication dans un congrès
IWOCA'09: International Workshop on Combinatorial Algorithms, pp.72-82, 2009, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432664
Contributeur : Christophe Paul <>
Soumis le : lundi 16 novembre 2009 - 19:41:34
Dernière modification le : jeudi 19 juillet 2018 - 11:54:04

Identifiants

  • HAL Id : lirmm-00432664, version 1

Collections

Citation

Stéphane Bessy, Anthony Perez, Christophe Paul. Polynomial Kernels for 3-Leaf Power Graph Modification Problems. IWOCA'09: International Workshop on Combinatorial Algorithms, pp.72-82, 2009, Lecture Notes in Computer Science. 〈lirmm-00432664〉

Partager

Métriques

Consultations de la notice

94