2009/05/05 by Serge Gaspers, Gaspers, Serge, Matthias Mnich +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #Limits and Structures in Graph Theory #cs.DM #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.0905.0567
openalex publication_date 2009/05/05 · arxiv created 2011/10/19 · arxiv updated 2011/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study combinatorial and algorithmic questions around minimal feedback vertex sets in tournament graphs. On the combinatorial side, we derive strong upper and lower bounds on the maximum number of minimal feedback vertex sets in an n-vertex tournament. We prove that every tournament on n vertices has at most 1.6740n minimal feedback vertex sets, and that there is an infinite family of tournaments, all having at least 1.5448n minimal feedback vertex sets. This improves and extends the bounds of Moon (1971). On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal feedback vertex sets of a tournament with polynomial delay. The combination of our results yields the fastest known algorithm for finding a minimum size feedback vertex set in a tournament.