Revisiting Path Contraction and Cycle Contraction

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 O^*(2ᵏ) time. This improves over the current algorithm known for the problem [Algorithmica 2014]. Cycle Contraction admits an algorithm running in O^*((2 + ε_)ᵏ) time where 0 < ε_ ≤ 0.5509 is inversely proportional to = 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 O^*(2.5191ⁿ)-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 O(n2-ε · 2ᵒ⁽ᵗʷ⁾) for any ε > 0, unless the Orthogonal Vectors Conjecture fails. Here, $tw$ is the treewidth of the input graph. The second result complements the O(nm)-time, i.e., O(n² · tw)-time, algorithm known for the problem [Discret. Appl. Math. 2014].