The new FIFA rules are hard: complexity aspects of sports competitions

Kern, W.; Paulusma, D.

Abstract

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 ( resp. ) but becomes NP-hard if the new rules ( resp. ) are applied. We determine the complexity of the above problem for all possible score allocation rules.

Citation

Kern, W., & Paulusma, D. (2001). The new FIFA rules are hard: complexity aspects of sports competitions. Discrete Applied Mathematics, 108(3), 317-323. https://doi.org/10.1016/s0166-218x%2800%2900241-9

• Journal Article Type: Article
• Publication Date: Mar 1, 2001
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 8, 2015
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Electronic ISSN: 1872-6771
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 108
• Issue: 3
• Pages: 317-323
• DOI: https://doi.org/10.1016/s0166-218x%2800%2900241-9
• Keywords: NP-complete; Network flow.
• Public URL: https://durham-repository.worktribe.com/output/1414988