[Back]

M. S. Ramanujan, S. Szeider:
"Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable";
Talk: Thirty-First AAAI Conference on Artificial Intelligence, Thirty-First AAAI Conference on Artificial Intelligence (invited); 2017-02-04 - 2017-02-09; in: "Thirty-First AAAI Conference on Artificial Intelligence", (2017), 3929 - 3935.

Single-elimination tournaments (or knockout tournaments) are a popular
format in sports competitions that is also widely used for decision
making and elections. In this paper we study the algorithmic problem
of manipulating the outcome of a tournament. More specifically, we
study the problem of find- ing a seeding of the players such that a
certain player wins the resulting tournament. The problem is known to
be NP-hard in general. In this paper we present an algorithm for this
problem that exploits structural restrictions on the tournament. More
specifically, we establish that the problem is fixed-parameter
tractable when parameterized by the size of a smallest feed- back arc
set of the tournament (interpreting the tournament as an oriented
complete graph). This is a natural parameter be- cause most problems
on tournaments (including this one) are either trivial or easily
solvable on acyclic tournaments, leading to the question-what about
nearly acyclic tournaments or tournaments with a small feedback arc
set? Our result signifi- cantly improves upon a recent algorithm by
Aziz et al. (2014) whose running time is bounded by an exponential
function where the size of a smallest feedback arc set appears in the
exponent and the base is the number of players.