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

Walter Kern; Daniël Paulusma

doi:10.1016/S0166-218X(00)00241-9

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

Walter Kern, Daniël Paulusma

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

19 Citations (Scopus)

56 Downloads (Pure)

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 (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.

Original language	English
Pages (from-to)	317-323
Number of pages	7
Journal	Discrete applied mathematics
Volume	108
Issue number	3
DOIs	https://doi.org/10.1016/S0166-218X(00)00241-9
Publication status	Published - 2001

Keywords

Network Flow
NP-complete

Access to Document

10.1016/S0166-218X(00)00241-9Licence: Other

Kern01newFinal published version, 95 KBLicence: Other

Cite this

@article{fb71d5f0e1a0431c9f6a29d6b4718daf,

title = "The new FIFA rules are hard: complexity aspects of sports competitions",

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 (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.",

keywords = "Network Flow, NP-complete",

author = "Walter Kern and Dani{\"e}l Paulusma",

year = "2001",

doi = "10.1016/S0166-218X(00)00241-9",

language = "English",

volume = "108",

pages = "317--323",

journal = "Discrete applied mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

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

AU - Kern, Walter

AU - Paulusma, Daniël

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

KW - Network Flow

KW - NP-complete

U2 - 10.1016/S0166-218X(00)00241-9

DO - 10.1016/S0166-218X(00)00241-9

M3 - Article

SN - 0166-218X

VL - 108

SP - 317

EP - 323

JO - Discrete applied mathematics

JF - Discrete applied mathematics

IS - 3

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this