Tournament Fixing Parameterized by Feedback Vertex Set Number Is FPT

Meirav Zehavi

Introduction

In the context of computational social choice, the Tournament Fixing Problem (TFP)—also known as the Tournament Seeding Problem—examines whether a tournament organizer can manipulate the outcome of a single-elimination tournament by strategically arranging the initial bracket. Given a tournament digraph $D$ representing the outcomes of all possible head-to-head matchups, the goal is to determine if there exists a seeding that allows a specific player $w$ to win.

While TFP is known to be NP-hard, researchers have long sought to identify structural parameters that make the problem tractable. This paper settles a significant open question by proving that TFP is Fixed-Parameter Tractable (FPT) when parameterized by the Feedback Vertex Set (FVS) number ($k$).

The Significance of the FVS Parameter

To understand the contribution of this work, it is helpful to compare the FVS number with the more commonly studied Feedback Arc Set (FAS) number.

  • FAS Number: The minimum number of match results (edges) that must be reversed to eliminate all cycles, turning the tournament into a transitive DAG (a perfect hierarchy).
  • FVS Number: The minimum number of players (vertices) that must be removed to eliminate all cycles.

The FVS number is a much more powerful and restrictive parameter because $k_{FVS} \le k_{FAS}$. A tournament might have a very large FAS number due to a single "chaos agent" who can beat many higher-ranked players, yet its FVS number would be 1. By proving the problem is FPT for FVS, the authors demonstrate that the complexity of rigging a tournament depends not on the total number of upsets, but on the number of players capable of causing them.

Algorithmic Framework

The authors' approach combines structural graph theory with dynamic programming, centered around the concept of a Binomial Arborescence (BA). A player $w$ can win a tournament if and only if $w$ is the root of a spanning BA within the tournament graph.

1. The Guessing Phase

Since the FVS ($F^*$) is small, the algorithm first identifies this set. It then "guesses" the relative positions of these $k$ players within the hypothetical winning BA. Using LCA-closure properties, the authors show that they only need to fix a skeleton structure of size $O(k)$ to capture the non-hierarchical interactions of the tournament.

2. Dynamic Programming and "Slots"

Once the FVS players are positioned, the remaining players—who form a Directed Acyclic Graph (DAG)—must be integrated. Because a DAG has a clear topological ordering (from strongest to weakest), the authors can use dynamic programming to greedily assign these players to the remaining "slots" in the binary tree. The core technical challenge involved defining these slots such that the DAG players could be tucked away without creating cycles that would invalidate the winning path for player $w$.

Key Results

The paper establishes that Tournament Fixing can be solved in $2^{O(k \log k)} \cdot n^{O(1)}$ time. This result is significant for several reasons:

  • Efficiency: The algorithm achieves a dependency on $k$ that matches the best-known algorithms for the (easier) FAS parameter.
  • Generality: It provides a unified framework that subsumes previous results related to nearly-transitive tournaments.
  • Constructive Nature: The proof is constructive; the algorithm can output the specific winning bracket rather than just a decision.

Conclusion and Future Directions

By proving that TFP is FPT with respect to the FVS number, this research shifts the focus of tournament complexity toward the number of "irregular" players. While the $2^{O(k \log k)}$ bound is efficient, future work may investigate whether a $2^{O(k)}$ algorithm is possible. Additionally, the authors suggest exploring even smaller parameters, such as directed treewidth, which could further broaden our understanding of when tournament outcomes can be effectively controlled.

Summary updated

Abstract

A knockout (or single-elimination) tournament is a format of a competition that is very popular in practice (particularly in sports, elections and decision making), and which has been extensively and intensively studied from a theoretical point of view for more than a decade. Particular attention has been devoted to the Tournament Fixing problem, where, roughly speaking, the objective is to determine whether we can conduct the knockout tournament in a way that makes our favorite player win. Here, part of the input is a tournament graph D that encodes the winner of each possible match. A sequence of papers has studied the parameterized complexity of Tournament Fixing with respect to the feedback arc set number (fas) of D Given that this parameter yielded tractability, it has been asked explicitly and repeatedly whether Tournament Fixing is FPT also with respect to the feedback vertex set number (fvs) of D. We answer this question positively. In fact, although fvs can be arbitrarily smaller than fas, we attain the same dependency on the parameter in the time complexity. So, additionally, our work subsumes the best known algorithm for Tournament Fixing with respect to as.
BibTeX
@inproceedings{zehavi2023tournament,
  author = {Meirav Zehavi},
  title = {{Tournament Fixing Parameterized by Feedback Vertex Set Number Is FPT}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25728},
}
Figure