Minimal and minimum feedback vertex sets in tournaments


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 n vertices has at most 1.6195n many minimal feedback vertex sets. Then we construct a tournament with 1.54486n 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 O(1.51071n) time.


back to EIDMA Seminar Combinatorial Theory announcements