2026-07-25T11:27:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16851 2024-03-06T10:58:29Z ddc:004 open_access

Approximation Algorithms for Covering Vertices by Long Paths Gong, Mingyang Fan, Jing Lin, Guohui Miyano, Eiji Path cover k-path local improvement amortized analysis approximation algorithm 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 ≤ 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 ≥ 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 performance analyses are done via amortization. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mingyang Gong and Jing Fan and Guohui Lin and Eiji Miyano 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.53 urn:nbn:de:0030-drops-168517 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.53 eng https://creativecommons.org/licenses/by/4.0/legalcode