Improved bounds for minimal feedback vertex sets in tournaments

Matthias Mnich*, Eva-Lotta Teutrine

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

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 languageEnglish
Pages (from-to)482-506
Number of pages25
JournalJournal of Graph Theory
Volume88
Issue number3
DOIs
Publication statusPublished - Jul 2018

Keywords

  • combinatorial bounds
  • exponential-time algorithms
  • feedback vertex sets
  • tournaments
  • ALGORITHMS

Cite this