Abstract
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 Martel [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 \( \mathcal{N}\mathcal{P} \)-complete. As a consequence, the generalized threshold result of Gusfield and Martel is of no use for the European football system since computing the corresponding threshold value is hard if \( \mathcal{P} \ne \mathcal{N}\mathcal{P} \). We also show that the elimination problem is still \( \mathcal{N}\mathcal{P} \)-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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
D. Gusfield and C. Martel, The Structure and Complexity of Sports Elimination Numbers, Tech. Report CSE-99-1, CS Department, Univ. of California, Davis, January 1999.
S. T. McCormick, Fast algorithms for parametric scheduling come from extensions to parametric maximum flow. In: Proc. of the 28th Annual ACM Symp. on the Theory of Computing (STOC), 319–328, 1996.
K. D. Wayne, A New Property and a Faster Algorithm for Baseball Elimination, In: Proc. of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999. Preprint available as a link under the URL http://www.cs.princeton.edu/~wayne/research.html
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bernholt, T., Gülich, A., Hofmeister, T., Schmitt, N. (1999). Football Elimination Is Hard to Decide Under the 3-Point-Rule. In: Kutyłowski, M., Pacholski, L., Wierzbicki, T. (eds) Mathematical Foundations of Computer Science 1999. MFCS 1999. Lecture Notes in Computer Science, vol 1672. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48340-3_37
Download citation
DOI: https://doi.org/10.1007/3-540-48340-3_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66408-6
Online ISBN: 978-3-540-48340-3
eBook Packages: Springer Book Archive