2-Approximating Feedback Vertex Set in Tournaments

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 F eedback V ertex S et problem in tournaments. Here the input is a tournament T and a weight function w: V ( T ) → ℕ 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 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.

Authors

• Daniel Lokshtanov
• Pranabendu Misra
• Joydeep Mukherjee
• Fahad Panolan
• Geevarghese Philip
• Saket Saurabh 0001

Keywords

No keywords are indexed for this paper.