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.5949(n) minimal FVS. This significantly improves the previously best upper bound of 1.6667(n) by Fomin etal. [STOC 2016] and 1.6740(n) by Gaspers and Mnich [J. Graph Theory72(1):72-89, 2013]. Our new upper bound almost matches the best-known lower bound of 21n/7 approximate to 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.5949(n)).
Original language | English |
---|---|
Pages (from-to) | 482-506 |
Number of pages | 25 |
Journal | Journal of Graph Theory |
Volume | 88 |
Issue number | 3 |
DOIs | |
Publication status | Published - Jul 2018 |
Keywords
- combinatorial bounds
- exponential-time algorithms
- feedback vertex sets
- tournaments
- ALGORITHMS