A 7/3-approximation for feedback vertex sets in tournaments. (English) Zbl 1397.68226

Sankowski, Piotr (ed.) et al., 24th annual European symposium on algorithms, ESA 2016, Aarhus, Denmark, August 22–24, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-015-6). LIPIcs – Leibniz International Proceedings in Informatics 57, Article 67, 14 p. (2016).
Summary: We consider the minimum-weight feedback vertex set problem in tournaments: given a tournament with non-negative vertex weights, remove a minimum-weight set of vertices that intersects all cycles. This problem is NP-hard to solve exactly, and Unique Games-hard to approximate by a factor better than 2. We present the first \(7/3\) approximation algorithm for this problem, improving on the previously best known ratio \(5/2\) given by M.-c. Cai et al. [SIAM J. Comput. 30, No. 6, 1993–2007 (2001; Zbl 0980.68053)].
For the entire collection see [Zbl 1351.68030].


68W25 Approximation algorithms
05C20 Directed graphs (digraphs), tournaments


Zbl 0980.68053
Full Text: DOI arXiv