On the Parameterized Complexity of Contraction to Generalization of Trees

摘要

For a family of graphs $cal F$, the $mathcal{F}$-Contraction problem takesas an input a graph $G$ and an integer $k$, and the goal is to decide if thereexists $S subseteq E(G)$ of size at most $k$ such that $G/S$ belongs to $calF$. Here, $G/S$ is the graph obtained from $G$ by contracting all the edges in$S$. Heggernes et al.~[Algorithmica (2014)] were the first to study edgecontraction problems in the realm of Parameterized Complexity. They studied$cal F$-Contraction when $cal F$ is a simple family of graphs such as treesand paths. In this paper, we study the $mathcal{F}$-Contraction problem, where$cal F$ generalizes the family of trees. In particular, we define thisgeneralization in a "parameterized way". Let $mathbb{T}_ell$ be the family ofgraphs such that each graph in $mathbb{T}_ell$ can be made into a tree bydeleting at most $ell$ edges. Thus, the problem we study is$mathbb{T}_ell$-Contraction. We design an FPT algorithm for$mathbb{T}_ell$-Contraction running in time$mathcal{O}((2sqrt(ell))^{mathcal{O}(k + ell)} cdot n^{mathcal{O}(1)})$.Furthermore, we show that the problem does not admit a polynomial kernel whenparameterized by $k$. Inspired by the negative result for the kernelization, wedesign a lossy kernel for $mathbb{T}_ell$-Contraction of size $mathcal{O}([k(k + 2ell)] ^{(lceil {rac{lpha}{lpha-1}ceil + 1)}})$.