Matthias Mnich

A tournament is a complete graph with orientations for all edges. A minimal feedback vertex set of a tournament is a subset of the vertices such that its deletion leaves a maximal induced acyclic subtournament. We show that any tournament on 1.54486 minimal feedback vertex sets. From the upper bound we derive an algorithm that solves the NP-hard Minimum Feedback Vertex Set Problem on Tournaments in ^{n}O(1.51071 time.
^{n}) |