  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.4394 k + 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.
