Approximately covering vertices by order-$5$ or longer paths

Abstract

This paper studies $MP{C}_v^{5+}$, which is to cover as many vertices as possible in a given graph $G=(V,E)$ by vertex-disjoint $5^{+}$-paths (i.e., paths each with at least five vertices). $MP{C}_v^{5+}$ is NP-hard and admits an existing local-search-based approximation algorithm which achieves a ratio of $\frac{19}{7}\approx 2.714$ and runs in $O(|V{|}^6)$ time. In this paper, we present a new approximation algorithm for $MP{C}_v^{5+}$ which achieves a ratio of $2.511$ and runs in $O(|V{|}^{2.5}|E{|}^2)$ time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion.

Full version of an extended abstract in COCOON 2024