Related Experiment Video
Updated: Feb 9, 2026
Movement Retraining using Real-time Feedback of Performance
Published on: January 17, 2013
Improved bounds for minimal feedback vertex sets in tournaments
M Mnich1,2, E Teutrine1
1Institut für Informatik Universität Bonn Bonn Germany.
Abstract:
We study feedback vertex sets (FVS) in tournaments, which are orientations of complete graphs. As our main result, we show that any tournament on n nodes has at most 1.5949 minimal FVS. This significantly improves the previously best upper bound of 1.6667 by Fomin et al. [STOC 2016] and 1.6740 by Gaspers and Mnich [J. Graph Theory72(1):72-89, 2013]. Our new upper bound almost matches the best-known lower bound of 21n/7≈1.5448n, due to Gaspers and Mnich. Our proof is algorithmic, and shows that all minimal FVS of tournaments can be enumerated in time O(1.5949n).
Related Concept Videos
00:46Feedback Inhibition
01:01Feedback Loops
01:24Effects of feedback
Feedback significantly modifies the gain of a control system. The gain of a system without feedback is altered by a factor of one plus GH, where G represents...
01:26Feedback control systems
Linear feedback systems are theoretical models that simplify analysis and design. These systems operate under the principle that their output is directly proportional to their input within certain ranges. For instance, an amplifier in a control system behaves linearly as long as the input signal remains within a specific range. However, most physical systems exhibit inherent nonlinearity...
01:24Facial Feedback Hypothesis
01:07Cell Signaling Feedback Loops
Negative feedback loops
Most signaling systems have negative feedback loops that can perform different functions such as output limiter, and adaptation.
Output limiter
Upon receiving an input signal, the cellular response rapidly increases until a threshold is reached. Beyond this threshold, a negative feedback loop...