This house proves that debating is harder than soccer

DOI10.4230/LIPICS.FUN.2016.25zbMATH Open1369.68245arXiv1605.03063OpenAlexW2962837824MaRDI QIDQ5282823FDOQ5282823

Authors: Stefan Neumann, Andreas Wiese 

Publication date: 17 July 2017

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.

Full work available at URL: https://arxiv.org/abs/1605.03063

Recommendations

• The computational complexity of the elimination problem in generalized sports competitions
• Soccer is Harder Than Football
• The new FIFA rules are hard: Complexity aspects of sports competitions.
• Fixing balanced knockout and double elimination tournaments
• The structure and complexity of sports elimination numbers

zbMATH Keywords

complexitysoccerdebatingelimination games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (7)

• Soccer is Harder Than Football
• The new FIFA rules are hard: Complexity aspects of sports competitions.
• Refining the complexity of the sports elimination problem
• A quest for a fair schedule: the international Young Physicists' Tournament
• A connection between sports and matroids: how many teams can we beat?
• The computational complexity of the elimination problem in generalized sports competitions
• A new property and a faster algorithm for baseball elimination

This page was built for publication: This house proves that debating is harder than soccer

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5282823)