Improved bounds for minimal feedback vertex sets in tournaments
Citation Link: https://doi.org/10.15480/882.2634
Publikationstyp
Journal Article
Date Issued
2017-12-08
Sprache
English
Author(s)
TORE-DOI
TORE-URI
Journal
Volume
88
Issue
3
Start Page
482
End Page
506
Citation
Journal of Graph Theory 88 (3): 482-506 (2018)
Publisher DOI
Publisher
Wiley-Blackwell
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.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).
Subjects
combinatorial bounds
exponential-time algorithms
feedback vertex sets
tournaments
DDC Class
004: Informatik