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

DOI10.4230/LIPICS.ESA.2016.67MaRDI QIDQ4606339zbMATH OpenOpenAlexFDO

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

Publication date 2 March 2018

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

zbMATH Keywords

approximation algorithmstournamentsfeedback vertex sets

Mathematics Subject Classification ID

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

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

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

Cited in

(14)

• A Min-Max Theorem on Tournaments
• Ranking tournaments with no errors. I: Structural description
• 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
• A (2+)-factor approximation algorithm for split vertex deletion
• Dynamic parameterized feedback problems 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

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)