2-Approximating Feedback Vertex Set in Tournaments

Lokshtanov, D and Misra, P and Mukherjee, J and Panolan, F. and et al, . (2021) 2-Approximating Feedback Vertex Set in Tournaments. ACM Transactions on Algorithms, 17 (2). pp. 1-14. ISSN 1549-6333

[img] Text
3446969.pdf - Published Version

Download (339kB)


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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Panolan, Fahadhttps://orcid.org/ 0000-0001-6213-8687
Item Type: Article
Uncontrolled Keywords: Approximation ratios, Feedback vertex set, Feedback Vertex Set problems, LP relaxation; Optimal solutions, Polynomial-time, Unique games conjecture, Weight functions
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Mrs Haseena VKKM
Date Deposited: 03 Nov 2021 07:15
Last Modified: 11 Mar 2022 05:47
URI: http://raiith.iith.ac.in/id/eprint/8861
Publisher URL: https://dl.acm.org/doi/10.1145/3446969
OA policy: https://v2.sherpa.ac.uk/id/publication/10668
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 8861 Statistics for this ePrint Item