2024/06/16 by Liu, Yuxi, Xiao, Mingyu
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2406.10829
The Co-Path/Cycle Packing problem (resp. The Co-Path 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 (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 3k. In 2015, Feng et al. provided an O^*(3k)-time randomized algorithms for both of them. Recently, Tsur showed that they can be solved in O^*(3k) 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 Co-Path/Cycle Packing can be solved in O^*(2.8192k) time deterministically and Co-Path Packing can be solved in O^*(2.9241k) time with failure probability ≤ 1/3. As a by-product, we also show that the Co-Path Packing problem can be solved in O^*(5p) time with probability at least 2/3 if a path decomposition of width p is given.