A 7/3-approximation for feedback vertex sets in tournaments

DOI10.4230/LIPICS.ESA.2016.67zbMATH Open1397.68226arXiv1511.01137OpenAlexW2962933009MaRDI QIDQ4606339FDOQ4606339

László A. Végh, Matthias Mnich, Virginia Vassilevska Williams

Publication date: 2 March 2018

Abstract: We consider the minimum-weight feedback vertex set problem in tournaments: given a tournament with non-negative vertex weights, remove a minimum-weight set of vertices that intersects all cycles. This problem is $mathsfNP$-hard to solve exactly, and Unique Games-hard to approximate by a factor better than 2. We present the first $7/3$ approximation algorithm for this problem, improving on the previously best known ratio $5/2$ given by Cai et al. [FOCS 1998, SICOMP 2001].

Full work available at URL: https://arxiv.org/abs/1511.01137

Recommendations

• An approximation algorithm for feedback vertex sets in tournaments
• A Min-Max Theorem on Tournaments
• Parameterized and Exact Computation
• Feedback vertex sets in tournaments
• Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments

zbMATH Keywords

approximation algorithmstournamentsfeedback vertex sets

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Approximation algorithms (68W25)

Cited In (13)

• Ranking tournaments with no errors. I: Structural description
• Improved approximation algorithms for hitting 3-vertex paths
• A tight approximation algorithm for the cluster vertex deletion problem
• A tight approximation algorithm for the cluster vertex deletion problem
• Improved bounds for minimal feedback vertex sets in tournaments
• A \(7 / 3\)-approximation algorithm for feedback vertex set in tournaments via Sherali-Adams
• Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number
• An approximation algorithm for feedback vertex sets in tournaments
• Tournaments and Semicomplete Digraphs
• Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number
• Quick-sort style approximation algorithms for generalizations of feedback vertex set in tournaments
• Triangle packing in (sparse) tournaments: approximation and kernelization
• A Min-Max Theorem on Tournaments

This page was built for publication: A 7/3-approximation for feedback vertex sets in tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606339)