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 (effi-
cient 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