On the Parameterized Complexity of Contraction to Generalization of Trees

Abstract

For a family of graphs $\mathcal{F}$, the $\mathcal{F}$-Contraction problem takes as an input a graph $G$ and an integer $k$, and the goal is to decide if there exists $S\subseteq E(G)$ of size at most $k$ such that $G/S$ belongs to $\mathcal{F}$. 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 edge contraction problems in the realm of Parameterized Complexity. They studied $\mathcal{F}$-Contraction when $\mathcal{F}$ is a simple family of graphs such as trees and paths. In this paper, we study the $\mathcal{F}$-Contraction problem, where $\mathcal{F}$ generalizes the family of trees. In particular, we define this generalization in a "parameterized way". Let ${\mathbb{T}}_{\ell }$ be the family of graphs such that each graph in ${\mathbb{T}}_{\ell }$ can be made into a tree by deleting 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}((2\sqrt{(}\ell ){)}^{\mathcal{O}(k+\ell )}\cdot n^{\mathcal{O}(1)})$. Furthermore, we show that the problem does not admit a polynomial kernel when parameterized by $k$. Inspired by the negative result for the kernelization, we design a lossy kernel for ${\mathbb{T}}_{\ell }$-Contraction of size $\mathcal{O}([k(k+2\ell ){]}^{(\lceil \frac{\alpha }{\alpha -1}\rceil +1)})$.

Full version of paper appeared in IPEC 2017