Find largest set of players that never played against eachother

Question

I have an interesting problem I need to solve. I have a list of about 200k two player matches containing about 22k unique players. I need to find the largest set of players that never played against each other.

The first approach I did:

1. pair each player with a set of players he played against
2. sort them by number of players played against (from min to max)
3. for each player, remove players played against from set of all players until the set is valid.

This approach got me a valid set of about 3000 players. How could I improve this? Thanks!

Answer 1

You are essentially asking to find a maximum independent set of the graph in which each vertex is a player and there is an edge between two players that played against each other.

Unfortunately, without additional restrictions, the maximum independent set problem cannot be approximated in polynomial time within any constant factor unless P=NP. In fact, it cannot even be approximated in polynomial time within a factor $n^{1-\varepsilon}$ for any constant $\varepsilon>0$ of choice (where $n$ is the number of vertices) unless ZPP=NP. See here.

Since you seem to be interested in one specific instance of the problem, you might try to use any readily available solver for max independent set/max clique and see how they perform. You could even write the problem as an integer linear program and use an ILP solver (although I would expect specialized tools to perform better).

Answer 2

Consider the players as a graph $G = (V, E)$ with $V$ being the set of all players and $(p_1, p_2) \in E$ if $p_1, p_2 \in V$ have not played against each other. Sets of players that have never played against each other are cliques of this graph, and you are looking for a maximum clique (a clique with the greatest number of member vertices). Alternatively, you can think of the edge representing that two players have played against each other and find a maximum independent set in the complement graph of $G$.

The best algorithms for finding maximum cliques or maximum independent sets in arbitrary graphs perform in exponential time with fairly small bases: Wikipedia lists a few approaches in their article on Clique problems. The asymptotically fastest algorithm currently known is described as follows:

Robson's algorithm combines a similar backtracking scheme [to Bron–Kerbosch algorithm] (with a more complicated case analysis) and a dynamic programming technique in which the optimal solution is precomputed for all small connected subgraphs of the complement graph. These partial solutions are used to shortcut the backtracking recursion. The fastest algorithm known today is a refined version of this method by Robson (2001) which runs in time $O(2^{0.249n})$ = $O(1.1888^n)$.

The Robson 2001 paper is available here. However, due to the large dataset, even these best algorithms may prove to inefficient due to the general difficulty of finding cliques or maximum independent sets.