Feedback vertex sets in tournaments

S. Gaspers, M. Mnich

Research output: Contribution to journalArticleAcademicpeer-review

26 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)72-89
JournalJournal of Graph Theory
Volume72
Issue number1
DOIs
Publication statusPublished - 2013

Fingerprint

Dive into the research topics of 'Feedback vertex sets in tournaments'. Together they form a unique fingerprint.

Cite this