hide
Free keywords:
Computer Science, Computational Complexity, cs.CC
Abstract:
During the last twenty years, a lot of research was conducted on the sport
elimination problem: Given a sports league and its remaining matches, we have
to decide whether a given team can still possibly win the competition, i.e.,
place first in the league at the end. Previously, the computational complexity
of this problem was investigated only for games with two participating teams
per game. In this paper we consider Debating Tournaments and Debating Leagues
in the British Parliamentary format, where four teams are participating in each
game. We prove that it is NP-hard to decide whether a given team can win a
Debating League, even if at most two matches are remaining for each team. This
contrasts settings like football where two teams play in each game since there
this case is still polynomial time solvable. We prove our result even for a
fictitious restricted setting with only three teams per game. On the other
hand, for the common setting of Debating Tournaments we show that this problem
is fixed parameter tractable if the parameter is the number of remaining rounds
$k$. This also holds for the practically very important question of whether a
team can still qualify for the knock-out phase of the tournament and the
combined parameter $k + b$ where $b$ denotes the threshold rank for qualifying.
Finally, we show that the latter problem is polynomial time solvable for any
constant $k$ and arbitrary values $b$ that are part of the input.
