A simple 7/3-approximation algorithm for feedback vertex set in tournaments

2020/08/20 by Aprile, Manuel, Drescher, Matthew, Fiorini, Samuel +1
#05C20 #52B12 #68W25 #90C05 #90C27 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2008.08779

Abstract

We show that performing just one round of the Sherali-Adams hierarchy gives an easy 7/3-approximation algorithm for the Feedback Vertex Set (FVST) problem in tournaments. This matches the best deterministic approximation algorithm for FVST due to Mnich, Williams, and Végh, and is a significant simplification and runtime improvement of their approach.

Related

• A 7/3-Approximation for Feedback Vertex Sets in Tournaments
• A 2-Approximation Algorithm for Feedback Vertex Set in Tournaments
• Quick-Sort Style Approximation Algorithms for Generalizations of Feedback Vertex Set in Tournaments
• Feedback Vertex Sets in Tournaments
• Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Tournaments