A polynomial kernel for $3$-leaf power deletion

Abstract

For a non-negative integer $\ell$, the $\ell$-leaf power of a tree $T$ is a simple graph $G$ on the leaves of $T$ such that two vertices are adjacent in $G$ if and only if their distance in $T$ is at most $\ell$. We provide a polynomial kernel for the problem of deciding whether we can delete at most $k$ vertices to make an input graph a $3$-leaf power of some tree. More specifically, we present a polynomial-time algorithm for an input instance $(G,k)$ for the problem to output an equivalent instance $(G^{\prime },k^{\prime })$ such that $k^{\prime }\le k$ and $G^{\prime }$ has at most $O(k^{14})$ vertices.

arXiv comment28 pages, 1 figure

References in corpus (1)

• Parameterized Leaf Power Recognition via Embedding into Graph Products