Options
Feedback vertex sets in tournaments
Publikationstyp
Journal Article
Date Issued
2012-06-26
Sprache
English
Author(s)
TORE-URI
Journal
Volume
72
Start Page
72
End Page
89
Citation
Journal of Graph Theory (2012)
Publisher DOI
Publisher
Wiley-Blackwell
We study combinatorial and algorithmic questions around minimal feedback vertex sets (FVS) in tournament graphs. On the combinatorial side, we derive upper and lower bounds on the maximum number of minimal FVSs in an n‐vertex tournament. We prove that every tournament on n vertices has at most 1.6740n minimal FVSs, and that there is an infinite family of tournaments, all having at least 1.5448n minimal FVSs. This improves and extends the bounds of Moon (1971). On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal FVSs of a tournament with polynomial delay. The combination of our results yields the fastest known algorithm for finding a minimum‐sized FVS in a tournament.
DDC Class
004: Informatik