Paths to Trees and Cacti

Abstract We know that Tree Contraction does not admit a polynomial kernel unless NP ⊆ coNP/poly , while Path Contraction admits a kernel with O ( k ) vertices. The starting point of this article is the following natural questions: What is the structure of the family of paths that allows Path Contraction to admit a polynomial kernel? Apart from the size of the solution, what other additional parameters should we consider so we can design polynomial kernels for these basic contraction problems? To design polynomial kernels, we consider the family of trees with the bounded number of leaves (note that the family of paths are trees with at most two leaves). In particular, we study Bounded Tree Contraction . Here, an input is a graph G, integers k and l, and the goal is to decide whether, there is a subset F ⊆ E ( G ) of size at most k such that G / F is a tree with at most l leaves. We design a kernel with O ( k l ) vertices and O ( k 2 + k l ) edges for this problem. We complement this result by giving kernelization lower bound. We also prove similar results for Bounded Out-Tree Contraction and Bounded Cactus Contraction .