A 2-Approximation Algorithm for Feedback Vertex Set in Tournaments

09/22/2018
by   Daniel Lokshtanov, et al.
0

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). 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset