pipette
ENEnglish

Layering and reverse extension for weighted -path vertex cover

Jiajing Wu, An Zhang, Shiming Li, Guohui Lin

Preprint

En palabras de los autores

We study the weighted -path vertex cover problem for any fixed integer , in which a vertex non-negatively weighted simple graph is given and one wants to find a minimum-weight vertex subset such that every simple path on vertices in contains at least one vertex of . The problem generalizes the classic weighted vertex cover problem, that is, , and it admits a -approximation algorithm of Hochbaum~[SIAM J. Comput., 1982] and a -approximation algorithm of Br\"ustle 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 for odd and of ratio for even . When and , these ratios are and , respectively, matching the state-of-the-art approximation ratios for the corresponding special cases.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 13 pages; submitted for publication