Mnich, MatthiasMatthiasMnichTeutrine, Eva LottaEva LottaTeutrine2020-01-242020-01-242017-12-08Journal of Graph Theory (2018)http://hdl.handle.net/11420/4534We 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.6667^n by Fomin et al. [STOC 2016] and 1.6740^n by Gaspers and Mnich [J. Graph Theory 72(1):72–89, 2013]. Our new upper bound almost matches the best-known lower bound of 21^n/7≈1.5448^n, due to Gaspers and Mnich. Our proof is algorithmic, and shows that all minimal FVS of tournaments can be enumerated in time O(1.5949^n).en0364-9024Journal of graph theory20173482506Wiley-Blackwellhttps://creativecommons.org/licenses/by/4.0/combinatorial boundsexponential-time algorithmsfeedback vertex setstournamentsInformatikImproved bounds for minimal feedback vertex sets in tournamentsJournal Articleurn:nbn:de:gbv:830-882.06489210.15480/882.263410.1002/jgt.2222510.15480/882.2634Other