Revisiting Path Contraction and Cycle Contraction

Abstract

The Path Contraction and Cycle Contraction problems take as input an undirected graph $G$ with $n$ vertices, $m$ edges and an integer $k$ and determine whether one can obtain a path or a cycle, respectively, by performing at most $k$ edge contractions in $G$. We revisit these NP-complete problems and prove the following results. Path Contraction admits an algorithm running in ${\mathcal{O}}^{\ast }(2^k)$ time. This improves over the current algorithm known for the problem [Algorithmica 2014]. Cycle Contraction admits an algorithm running in ${\mathcal{O}}^{\ast }((2+\hat{I}{\mu }_{\ell }{)}^k)$ time where $0<\hat{I}{\mu }_{\ell }\le 0.5509$ is inversely proportional to $\ell =n-k$. Central to these results is an algorithm for a general variant of Path Contraction, namely, Path Contraction With Constrained Ends. We also give an ${\mathcal{O}}^{\ast }(2.5191^n)$-time algorithm to solve the optimization version of Cycle Contraction. Next, we turn our attention to restricted graph classes and show the following results. Path Contraction on planar graphs admits a polynomial-time algorithm. Path Contraction on chordal graphs does not admit an algorithm running in time $\mathcal{O}(n^{2-\hat{I}\mu }\cdot 2^{o(tw)})$ for any $\hat{I}\mu >0$, unless the Orthogonal Vectors Conjecture fails. Here, $tw$ is the treewidth of the input graph. The second result complements the $\mathcal{O}(nm)$-time, i.e., $\mathcal{O}(n^2\cdot tw)$-time, algorithm known for the problem [Discret. Appl. Math. 2014].