Solving Co-Path/Cycle Packing Faster than 3ᵏ

The Co-Path/Cycle Packing 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. Co-Path/Cycle Packing is a fundamental graph problem that has important applications in bioinformatics. Although this problem has been extensively studied in parameterized algorithms, it seems hard to break the running time bound 3ᵏ. In 2015, Feng et al. provided an O^* (3ᵏ) -time randomized algorithm. Recently, Tsur showed that this problem can be solved in O^* (3ᵏ) time deterministically. In this paper, by combining several techniques such as path decomposition, dynamic programming, and branch-and-search methods, we show that Co-Path/Cycle Packing can be solved in O^* (2. 8192ᵏ) time. As a by-product, we also show that the d-Bounded-Degree Vertex Deletion problem, a generalization of Co-Path/Cycle Packing, can be solved in O^* ( (d + 2) ᵖ) time if a path decomposition of width p is given, which implies that d-Bounded-Degree Vertex Deletion is FPT with parameter p+d.