6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Here's an optimal, $O(1)$ algorithm: return the empty tournament. It minimizes the number of unused courts and satisfies all constraints. Seriously though, such objective function makes no sense if you don't give as an input a number of games to be played. If, instead, it has bi-objective function (maximize the number of games, minimize the number of unused court) you'd need to scalarize the problem, and is not properly defined at the moment. $\endgroup$ – R B Mar 12 '14 at 8:21
  • $\begingroup$ Thanks, I've updated with a hopefully more helpful definition of "optimal fixture". $\endgroup$ – Jeffrey Kemp Mar 12 '14 at 8:25
  • $\begingroup$ On second thought, I think the "maximum number of games" should be determined as a constraint... will edit accordingly. $\endgroup$ – Jeffrey Kemp Mar 12 '14 at 8:27
  • $\begingroup$ I've edited to make it clearer that there is only one variable to optimise, the number of games per entrant is fixed at the maximum number possible (while still satisfying the other constraints). $\endgroup$ – Jeffrey Kemp Mar 12 '14 at 8:30
  • $\begingroup$ If the inputs are given in unary, then the set of well-formed inputs is sparse, in which case {your problem is NP-hard w.r.t. many-one reductions computable in P implies P = NP} and {{your problem is NP-hard w.r.t. Turing reductions computable in P/poly} implies {NP $\subseteq$ P/poly}}. $\:$ However, it's still plausible that one might be able to show that if your problem is in P then E = NE. $\;\;\;\;$ $\endgroup$ – user12859 Mar 12 '14 at 8:39
1
$\begingroup$

At first glance, even a simple solution would appear to merely be ${\cal O}(n^2)$, which is obviously polynomial time. To make the rest of my answer more readable, I'm going to define the following variables:

numEntrants = the total number of entrants
largestNumEntrants = the number of entrants from the country with the most entrants
numRounds = numEntrants - largestNumEntrants

For the purposes of the rest of my answer, I will assume that numEntrants is even. If it is not even, then some odd number of entrants must have a bye each round and that greatly complicates matters when trying to make sure every entrant plays the exact same number of matches.

As you correctly observed in your question statement, the largest possible number of rounds is the total number of entrants minus the number of entrants from the country with the most. We can quickly observe that numRounds is in ${\cal O}$(numEntrants). Furthermore, the number of possible matches within a round is also in $\cal O$(numEntrants). Specifically, it is exactly numEntrants / 2.

My suggested solution would then be as follows:

Arrange the entrants in an ordered list (which I'll call entrantList) in such an order that all of the entrants from a particular country are adjacent to each other.

for (int round = 0; round < numRounds; round++)
{
    for (int i = 0; i < (numEntrants / 2); i++)
    {
         Match entrantList[i] with 
             entrantList[(i + largestNumEntrants + round) % numEntrants] for round.
    }
}

This algorithm clearly runs in $\cal O$(numEntrants$^2$) time and, as far as I understand them, satisfies all of your constraints, at least when numEntrants is even. Obviously, ${\cal O}(n^2)$ means that the problem is in P and is definitely not NP-Hard or NP-Complete.

This algorithm ensures that each entrant plays each other entrant a maximum of 1 time because it simply selects the entrant after the one it was previously matched with on each iteration. It ensures that no entrant from the same country plays another entrant from the same country because all entrants from the same country are adjacent to each other in the list and it starts with an offset of largestNumEntrants.

$\endgroup$
  • 1
    $\begingroup$ (By the way, you can use backticks `...` to include short code snippets, such as variable names, in running text, which makes typing an answer like this easier. For longer segments of code, you can add four spaces at the beginning of each line, instead of using PRE tags, though I'm not sure that gains much. You can also use LaTeX if you need it, though I don't think you did, for this post. Click the little question mark icon while you're editing for more details.) $\endgroup$ – David Richerby Mar 15 '14 at 9:20
  • $\begingroup$ In order to show that the problem is in P, you need to give a polynomial time algorithm that covers all inputs. $\endgroup$ – FrankW Mar 15 '14 at 9:25
  • $\begingroup$ Sorry it's taken so long to get back to your proposed answer. I feel like it's on the right track but can't quite get it to work either. When I run your algorithm with the sample data set, I get the following matches: 1. AU1vUK1 AU2vUK2 SA1vUK3 2. AU1vUK2 AU2vUK3 SA1vAU1 3. AU1vUK3 AU2vAU1 SA1vAU2 which violates some of the constraints (e.g. AU1 plays twice in round 2, and AU1 plays AU2 in round 3) $\endgroup$ – Jeffrey Kemp Mar 22 '14 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.