Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth
This resolves a long-standing open problem for researchers in parameterized algorithms by derandomizing the Cut & Count technique for these two problems.
The paper provides deterministic single exponential time algorithms for Co-Path Packing and Co-Path Set parameterized by treewidth, resolving an open question. The algorithms achieve O*(4^{tw}) time for Co-Path Set and O*(5^{pw}) time for Co-Path Packing, matching the previous randomized bounds.
The \textsc{Co-Path Packing} (resp., \textsc{Co-Path Set}) problem asks whether a given graph can be edited to a collection of induced paths by deleting at most $k$ vertices (resp., $k$ edges). Both are fundamental problems with significant applications in bioinformatics and have been extensively studied within the framework of exact and parameterized algorithms. Currently, the state-of-the-art approach utilizes the randomized ``Cut \& Count'' technique, which solves \textsc{Co-Path Set} in $O^*(4^{\mathbf{tw}})$ time and \textsc{Co-Path Packing} in $O^*(5^{\mathbf{pw}})$ time, where $\mathbf{tw}$ is treewidth and $\mathbf{pw}$ is pathwidth. However, as there is no known method to derandomize the ``Cut \& Count'' technique, the existence of deterministic single exponential time algorithms for these problems parameterized by treewidth has remained an open question. In this paper, we resolve this gap by providing deterministic single exponential time algorithms for both problems when parameterized by treewidth.