2016/03/14 by Blair D. Sullivan, Sullivan, Blair D., Andrew van der Poel +1
Computer Science · #68R10 #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #G.2.2
paper · pdf · doi:10.48550/arxiv.1603.04376
openalex publication_date 2016/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The k-CO-PATH SET problem asks, given a graph G and a positive integer k, whether one can delete k edges from G so that the remainder is a collection of disjoint paths. We give a linear-time fpt algorithm with complexity O^*(1.588k) for deciding k-CO-PATH SET, significantly improving the previously best known O^*(2.17k) of Feng, Zhou, and Wang (2015). Our main tool is a new O^*(4tw(G)) algorithm for CO-PATH SET using the Cut&Count framework, where tw(G) denotes treewidth. In general graphs, we combine this with a branching algorithm which refines a 6k-kernel into reduced instances, which we prove have bounded treewidth.