arXiv preprint ·
Layering and reverse extension for weighted $k$-path vertex cover
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 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 $\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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Four-Coloring Planar Graphs in Linear Time
Degree Realization with Maximum Matching
The C-3PO Framework: Algorithms for $\#\mathrm{BIS}$-Hard Problems on Graphs with Low Threshold Rank or High Girth
Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
Two choices suffice: $k$-out sampling leaves $O(n/k)$ intercomponent edges for $k\geq 2$
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.