A Single Exponential-Time FPT Algorithm for Cactus Contraction

For a collection $\mathcal{F}$ of graphs, the $\mathcal{F}$-$\text{textsc}Contraction$ problem takes a graph $G$ and an integer $k$ as input and decides if $G$ can be modified to some graph in $\mathcal{F}$ using at most $k$ edge contractions. The $\mathcal{F}$-$\text{textsc}Contraction$ problem is \NP-Complete for several graph classes $\mathcal{F}$. Heggerners et al. [Algorithmica, 2014] initiated the study of $\mathcal{F}$-$\text{textsc}Contraction$ in the realm of parameterized complexity. They showed that it is \FPT\ if $\mathcal{F}$ is the set of all trees or the set of all paths. In this paper, we study $\mathcal{F}$-$\text{textsc}Contraction$ where $\mathcal{F}$ is the set of all cactus graphs and show that we can solve it in $2^{\text{calO}(k)}\cdot \mathrm{\mid }V(G){\mathrm{\mid }}^{\text{OO}(1)}$ time.