We consider the problem to cover the maximum number of vertices in a graph using a collection of vertex-disjoint long paths, where by “long” each path has at least four vertices. We propose a simple local search operation to examine the neighborhoods of up to four extra vertices for every pair of existing paths to seek for improvement, resulting in an \(O(|V|^7)\) -time \(\frac{5}{3}\) -approximation algorithm. The performance analysis is done via a delicate amortization scheme, in which the vertices in the computed solution are partitioned into four groups in order to receive tokens from the optimal solution. The novelty in the amortization scheme is to allow a vertex with a larger group index to receive more tokens than a vertex with a smaller group index, so that for each path in the computed solution, its total received tokens are well balanced and are shown to be no more than \(\frac{5}{3}\) times its order.