Feedback Vertex Sets in Tournaments

Details Feedback Vertex Sets in Tournaments Feedback Vertex Sets in Tournaments

2009-05-05

arxiv.org/abs/0905.0567v3

Computer Science

Discrete Mathematics

Scientific paper

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.6740^n minimal feedback vertex sets, and that there is an infinite family of tournaments, all having at least 1.5448^n 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.

Affiliated with

Also associated with

No associations

Rating

Feedback Vertex Sets in Tournaments does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Feedback Vertex Sets in Tournaments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Feedback Vertex Sets in Tournaments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-450498