Improved bounds for minimal feedback vertex sets in tournaments
Matthias Mnich, Eva-Lotta Teutrine · Journal of Graph Theory · 2017
Abstract We study feedback vertex sets (FVS) in tournaments, which are orientations of complete graphs. As our main result, we show that any tournament on n nodes has at most 1.5949n minimal FVS. This significantly improves the previously best upper bound of 1.6667n by Fomin et al. [STOC 2016] and 1.6740n by Gaspers and Mnich [J. Graph Theory 72(1):72–89, 2013]. Our new upper bound almost matches the best‐known lower bound of , due to Gaspers and Mnich. Our proof is algorithmic, and shows that all minimal FVS of tournaments can be enumerated in time .