Layering and reverse extension for weighted k-path vertex cover

We study the weighted k-path vertex cover problem for any fixed integer k ≥ 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-14 for odd k ≥ 3 and of ratio 3k4 for even k ≥ 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.