A deterministic $(2+\epsilon )$-approximation for directed feedback vertex sets in tournaments

Ebrahim Ghorbani, Matthias Mnich

We nearly settle the polynomial-time approximability of the Directed Feedback Vertex Set problem in tournaments. This problem is Vertex Cover-hard, and thus cannot have a $(2 - \va…