Layering and reverse extension for weighted k-path vertex cover

arXiv:2610.40281 · cs.DS, cs.DM · Submitted 2026-10-29 · Read on arXiv

cs.DS, cs.DM

Submitted: 2026-10-29

Updated: 2026-10-29

Comments: 13 pages; submitted for publication

License: http://creativecommons.org/licenses/by/4.0/

The gist: We study the weighted k-path vertex cover problem for any fixed integer k at least 2, in which a vertex non-negatively weighted simple graph G = (V…

Abstract

We study the weighted k-path vertex cover problem for any fixed integer k at least 2, in which a vertex non-negatively weighted simple graph G = (V, E) is given and one wants to find a minimum-weight vertex subset C V such that every simple path on k vertices in G contains at least one vertex of C. The problem generalizes the classic weighted vertex cover problem, that is, k = 2, and it admits a k-approximation algorithm of Hochbaum [SIAM J. Comput., 1982] and a (k - 12) -approximation algorithm of Brüstle et al. [IWOCA 2021]. In this paper, we carefully design local weight functions in the Layering and Reverse Extension local ratio framework of Bar-Yehuda et al. [ACM Comput. Surv., 2004], leading to an approximation algorithm of ratio 3k-1 4 for odd k at least 3 and of ratio 3k 4 for even k at least 4. When k = 3 and k = 4, these ratios are 2 and 3, respectively, matching the state-of-the-art approximation ratios for the corresponding special cases.

Related papers