Approximation algorithms for covering vertices by long paths

Abstract

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seemingly escapes from the literature. A path containing at least $k$ vertices is considered long. When $k\le 3$, the problem is polynomial time solvable; when $k$ is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed $k\ge 4$, the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a $k$-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when $k=4$, the problem admits a $4$-approximation algorithm which was presented recently. We propose the first $(0.4394k+O(1))$-approximation algorithm for the general problem and an improved $2$-approximation algorithm when $k=4$. Both algorithms are based on local improvement, and their theoretical performance analyses are done via amortization and their practical performance is examined through simulation studies.

27 pages; an extended abstract appears in MFCS 2022