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

Text
3446969.pdf - Published Version
Download (339kB)

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.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Panolan, Fahad	https://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://raiithold.iith.ac.in/id/eprint/8861