A simple 7/3-approximation algorithm for feedback vertex set in tournaments
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.
14 pages, 4 figures