Header menu link for other important links
X
2-approximating feedback vertex set in tournaments
D. Lokshtanov, P. Misra, J. Mukherjee, , G. Philip, S. Saurabh
Published in Association for Computing Machinery
2020
Volume: 2020-January
   
Pages: 1010 - 1018
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) = Pv∈S w(v). Rounding optimal solutions to the natural LP-relaxation of this problem yields a simple 3-approximation 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 paper we give the first polynomial time factor 2 approximation algorithm for this problem. Assuming the Unique Games conjecture, this is the best possible approximation ratio achievable in polynomial time. Copyright © 2020 by SIAM
About the journal
JournalData powered by TypesetProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherData powered by TypesetAssociation for Computing Machinery