Improved bounds for minimal feedback vertex sets in tournaments.

We study feedback vertex sets (FVS) in tournaments, which are orientations of complete graphs. As our main result, we show that any tournament on nodes has at most 1.5949 minimal FVS. This significantly improves the previously best upper bound of 1.6667 by Fomin et al. [STOC 2016] and 1.6740 by Gaspers and Mnich [(1):72-89, 2013]. Our new upper bound almost matches the best-known lower bound of 21n/7≈1.5448n, due to Gaspers and Mnich. Our proof is algorithmic, and shows that all minimal FVS of tournaments can be enumerated in time O(1.5949n).