Approximately covering vertices by order-$5$ or longer paths
<|reference_start|>Approximately covering vertices by order-$5$ or longer paths: This paper studies $MPC^{5+}_v$, 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). $MPC^{5+}_v$ 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 $MPC^{5+}_v$ 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.<|reference_end|>
@article{gong2024approximately,
    title={Approximately covering vertices by order-$5$ or longer paths},
    author={Mingyang Gong, Zhi-Zhong Chen, Guohui Lin, and Lusheng Wang},
    journal={arXiv preprint arXiv:2408.11225},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.11225},
    primaryClass={cs.DS cs.DM}
}