An improved approximation algorithm for covering vertices by $$4^+$$ 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 $$\hbox {MPC}^{{4}+}_v$$ MPC v 4 + , to cover as many vertices in a given graph $$G = (V, E)$$ 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|^8)$$ O ( | V | 8 ) -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|^2|V|^2, |V|^5\})$$ O ( min { | E | 2 | V | 2 , | V | 5 } ) -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 M of G is relatively large compared to that in an optimal solution of $$\hbox {MPC}^{{4}+}_v$$ MPC v 4 + . Our new algorithm forms a feasible solution of $$\hbox {MPC}^{{4}+}_v$$ MPC v 4 + from a maximum matching M by computing a maximum-weight path-cycle cover in an auxiliary graph to connect as many edges in M as possible.