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 otherduring a round, an entrant can only play in a single matchno entrant wants to compete in a match against another entrant from the same countryno entrant wants to compete against another entrant more than once in the tournamenteach entrant must play the exact same number of matches overallthe 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 #2UK #1, #2 and #3SA #1The possible matches in this (artificially small) case are:AU1 v. UK1   AU1 v. UK2   AU1 v. UK3   AU1 v. SAAU2 v. UK1   AU2 v. UK2   AU2 v. UK3   AU2 v. SAUK1 v. SA    UK2 v. SA    UK3 v. SASince 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 3Round 1   AU1 v. UK1   AU2 v. UK2   UK3 v. SARound 2   AU1 v. UK2   AU2 v. UK3   UK1 v. SARound 3   AU1 v. UK3   AU2 v. UK1   UK2 v. SAThis 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.OutputThe 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.
Is building this tournament fixture an NP-Hard / NP-Complete problem?
complexity theory;np hard