An Approximation Algorithm for Feedback Vertex Sets in Tournaments
- 1 January 2001
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 30 (6) , 1993-2007
- https://doi.org/10.1137/s0097539798338163
Abstract
We obtain a necessary and sufficient condition in terms of forbidden structures for tournaments to possess the min-max relation on packing and covering directed cycles, together with strongly polynomial time algorithms for the feedback vertex set problem and the cycle packing problem in this class of tournaments. Applying the local ratio technique of Bar-Yehuda and Even to the forbidden structures, we find a 2.5-approximation polynomial time algorithm for the feedback vertex set problem in any tournament.published_or_final_versioKeywords
This publication has 7 references indexed in Scilit:
- One for the Price of Two: a Unified Approach for Approximating Covering ProblemsAlgorithmica, 2000
- Approximating Minimum Feedback Sets and Multicuts in Directed GraphsAlgorithmica, 1998
- Primal-Dual Approximation Algorithms for Feedback Problems in Planar GraphsCombinatorica, 1998
- On a conjecture of Tuza about packing and covering of trianglesDiscrete Mathematics, 1995
- Packing directed circuits fractionallyCombinatorica, 1995
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Ramsey numbers and an approximation algorithm for the vertex cover problemActa Informatica, 1985