Skip to Main content Skip to Navigation
Conference papers

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}.
Document type :
Conference papers
Complete list of metadata
Contributor : Christophe Paul <>
Submitted on : Monday, November 16, 2009 - 7:41:34 PM
Last modification on : Wednesday, August 28, 2019 - 1:34:00 PM


  • HAL Id : lirmm-00432664, version 1



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. ⟨lirmm-00432664⟩



Record views