Lokshtanov, D and Misra, P and Mukherjee, J and Panolan, F. and et al, .
(2021)
2Approximating Feedback Vertex Set in Tournaments.
ACM Transactions on Algorithms, 17 (2).
pp. 114.
ISSN 15496333
Abstract
A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T − S is acyclic. We consider the Feedback Vertex Set problem in tournaments. Here, the input is a tournament T and a weight function w : V(T) → N, and the task is to find a feedback vertex set S in T minimizing w(S) = ∑v∈S w(v). Rounding optimal solutions to the natural LPrelaxation of this problem yields a simple 3approximation algorithm. This has been improved to 2.5 by Cai et al. [SICOMP 2000], and subsequently to 7/3 by Mnich et al. [ESA 2016]. In this article, we give the first polynomial time factor 2approximation algorithm for this problem. Assuming the Unique Games Conjecture, this is the best possible approximation ratio achievable in polynomial time.
[error in script]
Actions (login required)

View Item 