An approximation algorithm or feedback vertex sets in tournaments

Citation
Mc. Cai et al., An approximation algorithm or feedback vertex sets in tournaments, SIAM J COMP, 30(6), 2000, pp. 1993-2007
Citations number
18
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
00975397 → ACNP
Volume
30
Issue
6
Year of publication
2000
Pages
1993 - 2007
Database
ISI
SICI code
0097-5397(20000418)30:6<1993:AAAOFV>2.0.ZU;2-4
Abstract
We obtain a necessary and sufficient condition in terms of forbidden struct ures for tournaments to possess the min-max relation on packing and coverin g directed cycles, together with strongly polynomial time algorithms for th e feedback vertex set problem and the cycle packing problem in this class o f tournaments. Applying the local ratio technique of Bar-Yehuda and Even to the forbidden structures, we nd a 2.5-approximation polynomial time algori thm for the feedback vertex set problem in any tournament.