Improved bounds for minimal feedback vertex sets in tournaments

Area of Science:

• Graph Theory
• Combinatorics
• Computer Science

Background:

• Feedback vertex sets (FVS) are crucial in analyzing directed graphs.
• Tournaments, as specific orientations of complete graphs, present unique challenges for FVS computation.
• Existing upper bounds for minimal FVS in tournaments have been progressively refined.

Purpose of the Study:

• To establish a tighter upper bound for the number of minimal feedback vertex sets in tournaments.
• To develop an algorithmic approach for enumerating these minimal FVS.
• To advance the theoretical understanding of FVS complexity in graph structures.

Main Methods:

• The study employs an algorithmic proof technique.
• It focuses on analyzing the structure of tournaments and their minimal feedback vertex sets.
• The research involves computational complexity analysis.

Main Results:

• A new upper bound of 1.5949^n for minimal FVS in tournaments is proven.
• This bound significantly improves upon prior results (1.6667^n and 1.6740^n).
• The algorithm enumerates all minimal FVS in O(1.5949^n) time.

Conclusions:

• The new upper bound is close to the best-known lower bound, indicating a more precise understanding of FVS in tournaments.
• The algorithmic enumeration provides a practical tool for further research.
• This work contributes significantly to the field of combinatorial algorithms and graph theory.