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.

DOI: 10.1137/s0097539798338163