Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation)
Archontia C. Giannopoulou, Daniel Lokshtanov, Saket Saurabh, Ondřej Suchý · SIAM Journal on Discrete Mathematics · 2016
In the Tree Deletion Set problem the input is a graph $G$ together with an integer $k$. The objective is to determine whether there exists a set $S$ of at most $k$ vertices such that $G\setminus S$ is a tree. The problem is \tt NP-complete and even \tt NP-hard to approximate within any factor of $\text{OPT}^c$ for any constant $c$. In this paper we give an $\mathcal{O}(k^5)$ size kernel for the Tree Deletion Set problem. An appealing feature of our kernelization algorithm is a new reduction rule, based on systems of linear equations, that we use to handle the instances on which Tree Deletion Set is hard to approximate.