Deciding the validity of the score sequence of a soccer tournament
In a soccer tournament of n teams, every pair of teams plays one match. The winner gets 3 points, the loser gets 0, while both teams receive 1 point in case of a draw. Is there a polynomial algorithm to decide whether a given score sequence (a score for each team) can be the end result of a tournament?
Remarks
The problem was proposed by Antal Iványi. One may generalize the problem by assuming that the results of some of the matches are known. Dömötör Pálvölgyi[1] proved that this more general problem is NP-complete. However, if the winner gets 2 points instead of 3, then it can be solved as a graph orientation problem with prescribed in-degrees.
A related problem is the so-called elimination problem: at some stage of a soccer tournament, knowing the results of the matches played so far, decide whether a given team has a theoretical chance to win the tournament. Bernholt et al. [2] and independently Kern and Paulusma [3] proved that this problem is NP-complete.
References
- ↑ D. Pálvölgyi, Deciding Soccer Scores and Partial Orientations of Graphs, EGRES Technical Report No. 2008-03.
- ↑ T. Bernholt, A. Gülich, T. Hofmeister, N. Schmitt, I. Wegener, Komplexitätstheorie, effiziente Algorithmen und die Bundesliga, Informatik-Spektrum 25 (2002), 488-502.DOI link.
- ↑ W. Kern, D. Paulusma, The new FIFA rules are hard: complexity aspects of sports competitions, Discrete Applied Mathematics 108 (2001), 317-323. DOI link.
