A Polynomial Kernel for 3-Leaf Power Deletion

Abstract

For a non-negative integer t, the t-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 t. 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', k') such that k'= k and G' has at most O(k14) vertices.