On Succinct Encodings for the Tournament Fixing Problem

Sushmita Gupta, Saket Saurabh, Ramanujan Sridharan, Meirav Zehavi

Abstract

This paper establishes the first polynomial kernelization for the Tournament Fixing Problem (TFP) when parameterized by the feedback arc set number ($k$). By leveraging a novel SAT-based encoding strategy and the structural properties of binomial arborescences, the authors demonstrate that complex tournament instances can be efficiently compressed into a size polynomial in $k$. This result proves that efficient preprocessing is possible for this NP-hard problem, effectively reducing the search space to a manageable "kernel" without losing the ability to determine if a specific player can be rigged to win.

Introduction

In single-elimination (knockout) tournaments, the initial seeding—the determination of who plays whom in the first round—is a critical factor in the final outcome. The Tournament Fixing Problem (TFP) examines this from the perspective of an external agent (a "rigger") who knows the predicted outcomes of every possible match and seeks to arrange the seeding so that a specific favorite player, $v^*$, wins the entire tournament.

While TFP is known to be NP-hard in general, computational complexity research often seeks "parameters" that make such problems tractable. A natural parameter for tournaments is the feedback arc set number ($k$), which quantifies how much a tournament deviates from a perfectly transitive structure (where if A beats B and B beats C, then A beats C). Although previous work established that TFP is Fixed-Parameter Tractable (FPT) with respect to $k$, it remained an open question whether the problem admitted a polynomial kernel—a way to shrink a massive tournament into a version with size $poly(k)$ while preserving the answer.

Methods

The authors achieve polynomial compression through a novel SAT-based encoding strategy. Rather than applying traditional graph-reduction rules, they translate the TFP instance into a Boolean Satisfiability (SAT) formula that captures the essential constraints of the problem.

Structural Foundations: Binomial Arborescences

A key technical insight is that a player wins a tournament if and only if they are the root of a specific spanning tree structure called a binomial arborescence. For a tournament with $n = 2^h$ players, the winning structure is a binomial tree of order $h$. This structure provides a rigid skeleton for the SAT encoding to fill.

Figure 1: A binomial arborescence of order 4, representing the winning structure for player 1 in a 16-player tournament.

Player Types and Template Trees

To handle large $n$, the authors group players into a small number of "types" based on their behavior against "affected" players—those involved in the $k$ feedback arcs. They then utilize a template tree to represent the skeleton of a winning tournament. The SAT formula "guesses" a valid template and verifies if the available counts of player types can be "packed" into the template's slots.

Succinct Encoding

By using bit-string representations for player counts, the authors ensure the SAT formula's size depends polynomially on $k$ and only logarithmically on the total number of players $n$. Under the assumption that $k \log k \ge \log n$ (as the problem is otherwise trivial), this keeps the entire encoding bounded by a polynomial of $k$.

Key Results

The primary contribution of this work is the proof that TFP admits a polynomial kernel when parameterized by the feedback arc set number $k$. Specifically, the authors provide a routine that computes a SAT encoding where the number of clauses and variables is bounded polynomially in $k$, independent of the original tournament size $n$. This creates a formal kernelization pipeline: TFP $\to$ SAT $ o$ 3-SAT $ o$ TFP.

Beyond the theoretical kernel, the paper reframes tournament fixing as a resource allocation or packing problem. This perspective shift allows for the logarithmic efficiency that makes the $poly(k)$ bound possible.

Discussion and Future Work

While this result is a significant step forward, the authors note that the feedback arc set number is a relatively restrictive parameter. A major open challenge is finding a polynomial kernel for TFP parameterized by the feedback vertex set number, which is a smaller and more general parameter. Additionally, while the reduction is mathematically polynomial, the multi-step chain (TFP to SAT to 3-SAT back to TFP) may result in kernels that are large in practice. However, the succinct SAT encoding itself could be directly utilized by modern SAT solvers to solve TFP instances more efficiently than previous custom algorithms.

Summary updated

Abstract

Single-elimination tournaments are a popular format in competitive environments. The Tournament Fixing Problem (TFP), which is the problem of finding a seeding of the players such that a certain player wins the resulting tournament, is known to be NP-hard in general and fixed-parameter tractable when parameterized by the feedback arc set number of the input tournament (an oriented complete graph) of expected wins/loses. However, the existence of polynomial kernelizations (efficient preprocessing) for TFP has remained open. In this paper, we present the first polynomial kernelization for TFP parameterized by the feedback arc set number of the input tournament. We achieve this by providing a polynomial-time routine that computes a SAT encoding where the number of clauses is bounded polynomially in the feedback arc set number.
BibTeX
@inproceedings{gupta2019succinct,
  author = {Sushmita Gupta and Saket Saurabh and Ramanujan Sridharan and Meirav Zehavi},
  title = {{On Succinct Encodings for the Tournament Fixing Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/46},
}
Figure