Layering and reverse extension for weighted $k$-path vertex cover

Abstract

We study the weighted $k$-path vertex cover problem for any fixed integer $k\ge 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\subseteq 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-\frac{1}{2})$-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 $\frac{3k-1}{4}$ for odd $k\ge 3$ and of ratio $\frac{3k}{4}$ for even $k\ge 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.

arXiv comment13 pages; submitted for publication