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
2021
Volume: 17
   
Issue: 2
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) = ∑v∈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 article, 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. © 2021 ACM.
About the journal
JournalData powered by TypesetACM Transactions on Algorithms
PublisherData powered by TypesetAssociation for Computing Machinery
ISSN15496325
Open AccessNo