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