2-approximating feedback vertex set in tournaments

Lokshtanov, D. and Misra, P. and Mukherjee, J. and Panolan, Fahad and et al, . (2020) 2-approximating feedback vertex set in tournaments. In: 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, 5 January 2020through 8 January 2020, Salt Lake City.

Text
Discrete_Algorithms.pdf - Published Version
Restricted to Registered users only
Download (604kB) | Request a copy

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) = Pv∈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. Copyright © 2020 by SIAM

[error in script]

IITH Creators:

IITH Creators	ORCiD
Panolan, Fahad	https://orcid.org/0000-0001-6213-8687

Item Type:

Conference or Workshop Item (Paper)

Additional Information:

This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 819416 and No. 715744), the IFCAM project “Applications of graph homomorphisms” (MA/IFCAM/18/39), the Bergens Forsknings Stiftelse(BFS) under the grant”Putting Algorithms Into Practice” (No. 810564) and the Norwegian Research Foundation(NRF) under the grant”Parameterized Complexity for Practical Computing” (No. 274526d). The last author also acknowledges the support of Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.

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:

. LibTrainee 2021

Date Deposited:

20 Oct 2022 13:26

Last Modified:

20 Oct 2022 13:26

URI:

http://raiithold.iith.ac.in/id/eprint/11012