## 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].

### MSC:

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

### Keywords:

approximation algorithms; feedback vertex sets; tournaments

Zbl 0980.68053
Full Text: