An Approximation Algorithm for Covering Vertices by  \(4^+\) -Paths

This paper deals with the problem of finding a collection of vertex-disjoint paths in a given graph \(G=(V,E)\) such that each path has at least four vertices and the total number of vertices in these paths is maximized. The problem is NP-hard and admits an approximation algorithm which achieves a ratio of 2 and runs in \(O(|V|^8)\) time. The known algorithm is based on time-consuming local search, and its authors ask whether one can design a better approximation algorithm by a completely different approach. In this paper, we answer their question in the affirmative by presenting a new approximation algorithm for the problem. Our algorithm achieves a ratio of 1.874 and runs in \(O(\min \{|E|^2|V|^2, |V|^5\})\) time. Unlike the previously best algorithm, ours starts with a maximum matching M of G and then tries to transform M into a solution by utilizing a maximum-weight path-cycle cover in a suitably constructed graph.