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 @math . 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 @math where @math denotes the threshold rank for qualifying. Finally, we show that the latter problem is polynomial time solvable for any constant @math and arbitrary values @math that are part of the input.
The "baseball elimination problem" is a classic problem which has already been considered from the computational point of view in the 1960's. At some stage of the baseball season, there is a set of games which have already been played and there is another set of remaining games. The problem consists in determining for a given team whether or not they are already "eliminated", i.e., whether they can no longer become champions. Early solutions proposed a network flow approach which resulted in polynomial time algorithms. The interest in this kind of elimination problem was recently revived by Wayne [4] who proved an interesting threshold property which allows one to compute all eliminated teams simultaneously. Namely, there is a constant W* such that a team is eliminated if and only if it can no longer obtain W* or more points. Wayne also describes an algorithm for computing the threshold W* in polynomial time. Gusfield and Maxtel [2] have generalized the proof of the existence of a threshold to a more general setting which includes European football, where the "3-point-rule" is in effect, i.e., 3 points are awarded for a win and 1 point is awarded for a tie. In this paper, we show that determining the elimination of a European football team under the 3-point-rule is NP-complete. As a consequence, the generalized threshold result of Gusfield and Mairtel is of no use for the European football system since computing the corresponding threshold value is hard if P # NP. We also show that the elimination problem is still NP-complete if all teams have at most three remaining games each while the problem can be solved in polynomial time if each team has at most two remaining games. Consider a soccer competition among various teams playing against each other in pairs (matches) according to a previously determined schedule. At some stage of the competition one may ask whether a particular team still has a (theoretical) chance to win the competition. The complexity of this question depends on the way scores are allocated according to the outcome of a match. For example, the problem is polynomially solvable for the ancient FIFA rules (2:0 resp. 1:1) but becomes NP-hard if the new rules (3:0 resp. 1:1) are applied. We determine the complexity of the above problem for all possible score allocation rules. We show that deciding if a simple graph has a partial ori- entation of its edges such that all vertices have a prescribed in-, out- and undirected degree, is NP-complete even for planar graphs. We prove that two related questions are also NP-complete, one is the decision of whether a score vector of a soccer-tournament is legal or not (we know who played who so far, but do not know the outcomes), the other is about a special edge-coloring of 3-uniform hypergraphs. 