How Hard Is It to Rig a Tournament When Few Players Can Beat or Be Beaten by the Favorite?

Knockout tournaments are a widely used competition format in sports, elections, and decision-making processes. In such tournaments, players compete in successive rounds, with losers eliminated and winners advancing until a single champion remains. Given a tournament digraph $D$, which encodes the outcomes of all possible matches, and a designated player $v^* \in V(D)$, the Tournament Fixing problem (TFP) asks whether the tournament can be scheduled in a way that guarantees $v^*$ emerges as the winner. TFP is known to be NP-hard in general (AAAI'14), but is fixed-parameter tractable (FPT) when parameterized by structural measures such as the feedback arc set (fas) or feedback vertex set (fvs) number of the tournament digraph (AAAI'17; IJCAI'18; AAAI'23). In this paper, we introduce and study two new structural parameters: the number of players who can defeat $v^*$ (i.e., the in-degree of $v^*$, denoted $d^+$) and the number of players that $v^*$ can defeat (i.e., the out-degree of $v^*$, denoted $d^-$). These parameters are motivated by the observation that when either the in-degree or out-degree is zero, the problem becomes trivial. This leads to a natural question: can TFP be efficiently solved when $d^+$ or $d^-$ is small? We answer this question affirmatively by showing that TFP is FPT when parameterized by either the in-degree or out-degree of $v^*$. Our algorithm for the in-degree parameterization is particularly involved and technically intricate. Notably, the in-degree $d^+$ can remain small even when other structural parameters such as fas or fvs are large. Hence, our results offer a new perspective and significantly broaden the parameterized algorithmic understanding of the Tournament Fixing problem.