Premium
Improved bounds for minimal feedback vertex sets in tournaments
Author(s) -
Mnich M.,
Teutrine E.
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22225
Subject(s) - tournament , combinatorics , mathematics , upper and lower bounds , vertex (graph theory) , graph , discrete mathematics , mathematical analysis
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 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 of21 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 ) .