An improved approximation algorithm for covering vertices by 4⁺-paths

Path cover is one of the well-known NP-hard problems that has received much attention. In this paper, we study a variant of path cover, denoted by MPC_v⁴⁺, to cover as many vertices in a given graph G = (V, E) as possible by a collection of vertex-disjoint paths each of order four or above. The problem admits an existing O(|V|⁸)-time 2-approximation algorithm by applying several time-consuming local improvement operations (Gong et al.: Proceedings of MFCS 2022, LIPIcs 241, pp 53:1–53:14, 2022). In contrast, our new algorithm uses a completely different method and it is an improved O(min{|E|²|V|², |V|⁵})-time 1.874-approximation algorithm, which answers the open question in Gong et al. (2022) in the affirmative. An important observation leading to the improvement is that the number of vertices in a maximum matching Μ of G is relatively large compared to that in an optimal solution of MPC_v⁴⁺. Our new algorithm forms a feasible solution of MPC_v⁴⁺ from a maximum matching Μ by computing a maximum-weight path-cycle cover in an auxiliary graph to connect as many edges in Μ as possible. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2025.