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.
A major difference between baseball and soccer leagues is which outcomes are possible in a single game. For soccer leagues with the three-point-rule it was proven by @cite_14 and @cite_19 independently that it is -hard to determine whether a team can win the league. P 'alv "olgyi @cite_3 proved that when we are given the table of a soccer league and a list of games that were played so far without their outcomes, it is -hard to decide whether this table is valid, i.e., whether the distribution of points to the teams can be achieved by real outcomes of games. @cite_16 , the authors construct a hypergraph representing the teams and their remaining matches. Depending on certain properties of this graph they prove multiple hardness results for the question whether a certain team can still win the competition.
@cite_19 @cite_14 @cite_3 @cite_16
1980618969 1515766120 2042424886 1555156751
In the baseball elimination problem, there is a league consisting of n teams. At some point during the season, team i has wi wins and gij games left to play against team j. A team is eliminated if it cannot possibly finish the season in first place or tied for first place. The goal is to determine exactly which teams are eliminated. The problem is not as easy as many sports writers would have you believe, in part because the answer depends not only on the number of games won and left to play but also on the schedule of remaining games. In the 1960's, Schwartz showed how to determine whether one particular team is eliminated using a maximum flow computation. This paper indicates that the problem is not as difficult as many mathematicians would have you believe. For each team i, let gi denote the number of games remaining. We prove that there exists a value W* such that team i is eliminated if and only if wi + gi < W*. Using this surprising fact, we can determine all eliminated teams in time proportional to a single maximum flow computation in a graph with n nodes; this improves upon the previous best known complexity bound by a factor of n. 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. Identifying the teams that are already eliminated from contention for first place of a sports league, is a classic problem that has been widely used to illustrate the application of linear programming and network flow. In the classic setting each game is played between two teams and the first place goes to the team with the greatest total wins. Recently, two papers [W], [AEHO] detailed a surprising structural fact in the classic setting: At any point in the season, there is a computable threshold W such that for any team i , i is eliminated (has no chance to win or tie for first place) if and only if i cannot win W or more games. They used this threshold to speed up the identification of eliminated teams. In both papers the proofs of the existence of a threshold are tied to the computational methods used to find it.