Layering and reverse extension for weighted k-path vertex cover
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
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles