Polynomial Kernels for 3-Leaf Power Graph Modification Problems - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2009

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

Dates and versions

lirmm-00432664 , version 1 (16-11-2009)

Identifiers

  • HAL Id : lirmm-00432664 , version 1

Cite

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⟩
102 View
0 Download

Share

More