I'm curious to know if this problem is NP-Hard / NP-Complete, which I believe would mean I'm unlikely to find a polynomial-time algorithm to solve it.
I have written a program which randomly generates a tournament fixture, and I call it many times to try to pack the matches into the smallest number of rounds.
When it comes to complexity theory I am still a novice, so laymen's terms would be appreciated.
Inputs:
- a set of countries, each of which may enter one or more entrants to the tournament (e.g. Australia might enter two entrants, UK might enter three entrants, and South Africa might enter one entrant)
Constraints:
- each match consists of two entrants playing against each other
- during a round, an entrant can only play in a single match
- no entrant wants to compete in a match against another entrant from the same country
- no entrant wants to compete against another entrant more than once in the tournament
- each entrant must play the exact same number of matches overall
- the number of matches each entrant must play is determined by MIN(for each entrant, total number of possible matches that satisfy the other constraints)
For example, say we have the following entrants:
- AU #1 and #2
- UK #1, #2 and #3
- SA #1
The possible matches in this (artificially small) case are:
AU1 v. UK1 AU1 v. UK2 AU1 v. UK3 AU1 v. SA
AU2 v. UK1 AU2 v. UK2 AU2 v. UK3 AU2 v. SA
UK1 v. SA UK2 v. SA UK3 v. SA
Since we want each entrant to play the exact same number of games, the maximum number of games per entrant is three (this can be derived from the total number of entrants (6) less the number of entrants from the largest country (3)).
Since there are six entrants in total, and there are two entrants to each match, the maximum number of courts we can utilise in a round is 3.
A sample fixture is:
Court 1 Court 2 Court 3
Round 1 AU1 v. UK1 AU2 v. UK2 UK3 v. SA
Round 2 AU1 v. UK2 AU2 v. UK3 UK1 v. SA
Round 3 AU1 v. UK3 AU2 v. UK1 UK2 v. SA
This is a nice example because it's easy to find a solution where each entrant has played exactly 3 games each, and they all pack perfectly into 3 rounds across 3 courts. Two of the possible 11 matches have not been played, but we don't care. We sum the results from each entrant's 3 games to determine an overall ranking, which is then used to generate the finals matches.
I have other scenarios where there are more entrants and I have been unable to pack them so neatly, but by running my program many times it almost always finds a near-optimal packing where the number of rounds and unused courts is minimised.
Output
The first problem is if there is a polynomial-time algorithm to generate an optimal fixture.
The optimal fixture is defined by:
- minimum number of unused courts (which implies minimising the number of rounds)
The second problem is, given a fixture "A", how to determine if it is an optimal solution, i.e. is it possible to prove that there can exist no better packings for a given set of entrants. If "A" involves no unused courts in any round, then the answer for that one is clearly "Yes" - but if there are any unused courts in any round, the answer is, I think, difficult to derive.