Research output

A 7/3-Approximation for Feedback Vertex Sets in Tournaments

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Associated researcher

  • Mnich, M.

  • Vassilevska Williams, V.
  • Végh, L. A.


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 Cai et al. [FOCS 1998, SICOMP 2001].


  • Full text

    Final published version, 598 KB, PDF-document

View graph of relations


Original languageEnglish
Title of host publication24th Annual European Symposium on Algorithms (ESA 2016)
EditorsPiotr Sankowski, Christos Zaroliagis
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl
Number of pages14
Publication statusPublished - 2016

Publication series

NameLeibniz International Proceedings in Informatics
PublisherSchloss Dagstuhl