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}.