2026-07-20T05:59:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6409 2024-03-06T10:38:11Z ddc:004 open_access

A 7/3-Approximation for Feedback Vertex Sets in Tournaments Mnich, Matthias Vassilevska Williams, Virginia Végh, László A. Approximation algorithms feedback vertex sets tournaments 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthias Mnich and Virginia Vassilevska Williams and László A. Végh 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.67 urn:nbn:de:0030-drops-64098 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.67 eng https://creativecommons.org/licenses/by/3.0/legalcode