Research work · 2001
An Approximation Algorithm for Feedback Vertex Sets in Tournaments
Mao-cheng Cai, Xiaotie Deng, Wenan Zang
SIAM Journal on Computing
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.