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?
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 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.  and independently Kern and Paulusma  proved that this problem is NP-complete.
- 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.