Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than $3^k$

The $\text{textsc}Co-Path\mathrm{/}CyclePacking$ problem (resp. The $\text{textsc}Co-PathPacking$ problem) asks whether we can delete at most $k$ vertices from the input graph such that the remaining graph is a collection of induced paths and cycles (resp. induced paths). These two problems are fundamental graph problems that have important applications in bioinformatics. Although these two problems have been extensively studied in parameterized algorithms, it seems hard to break the running time bound $3^k$. In 2015, Feng et al. provided an $O^{\ast }(3^k)$-time randomized algorithms for both of them. Recently, Tsur showed that they can be solved in $O^{\ast }(3^k)$ time deterministically. In this paper, by combining several techniques such as path decomposition, dynamic programming, cut & count, and branch-and-search methods, we show that $\text{textsc}Co-Path\mathrm{/}CyclePacking$ can be solved in $O^{\ast }({2.8192}^k)$ time deterministically and $\text{textsc}Co-PathPacking$ can be solved in $O^{\ast }({2.9241}^k)$ time with failure probability $\le 1\mathrm{/}3$. As a by-product, we also show that the $\text{textsc}Co-PathPacking$ problem can be solved in $O^{\ast }(5^p)$ time with probability at least 2/3 if a path decomposition of width $p$ is given.