patternMinor
Game tournament program, NP complete?
Viewed 0 times
completegameprogramtournament
Problem
I have been trying to find a solution both theoretical and practical to my problem but I just can't. The question is you have x players that should play some rounds y of games in groups of 4. Now if a player was in a game with somebody else, he is not allowed to be ever again with that player in the same group. Now the question is give n groups that satisfy this conditions. With n being maximal amount of possible groups.
My first approach was to just take a player put him into a group, now for the next player check the array already_played_with_players of the first player for the second player if he's not in add him and add the players he played with to the already_played_with_players array. Proceed so too for the next two players. Then mark these 4 players as in a group and take the next player out of the pool and so on.
This is not some educational question, but a real world problem. I would like to organize a game tournament, but so that people meet new people and don't play with the same people again. I already ask multiple people mathematicians, physicians, computer scientist, but the solution was not really evident to anybody. So I was wondering if the problem is NP-complete? I know I would need to find a reduction from another NP-complete problem to my problem to prove that, but I don't even know how to formalize my problem exactly.
My first approach was to just take a player put him into a group, now for the next player check the array already_played_with_players of the first player for the second player if he's not in add him and add the players he played with to the already_played_with_players array. Proceed so too for the next two players. Then mark these 4 players as in a group and take the next player out of the pool and so on.
This is not some educational question, but a real world problem. I would like to organize a game tournament, but so that people meet new people and don't play with the same people again. I already ask multiple people mathematicians, physicians, computer scientist, but the solution was not really evident to anybody. So I was wondering if the problem is NP-complete? I know I would need to find a reduction from another NP-complete problem to my problem to prove that, but I don't even know how to formalize my problem exactly.
Solution
Your problem has been solved by Brouwer in 1979 in his paper Optimal Packings of $K_4$'s into a $K_n$. Quoting from his paper, let
$$
J(2,4,v) = \begin{cases} \lfloor \frac{v}{4} \lfloor \frac{v-1}{3} \rfloor\rfloor - 1 & \text{if } v \equiv 7 \text{ or } 10 \pmod{12}, \\
\lfloor \frac{v}{4} \lfloor \frac{v-1}{3} \rfloor\rfloor & \text{otherwise}. \end{cases}
$$
The maximal number of groups when there are $v$ players, denoted $D(2,4,v)$, is equal to $J(2,4,v)$ unless $v \in \{9,10,17\}$, in which case $D(2,4,v) = J(2,4,v)-1$, and unless $v \in \{8,11,19\}$, in which case $D(2,4,v) = J(2,4,v)-2$.
The more general case in which every pair can appear at most $\lambda$ times has been solved by Assaf in his paper The packing of pairs by quadruples.
$$
J(2,4,v) = \begin{cases} \lfloor \frac{v}{4} \lfloor \frac{v-1}{3} \rfloor\rfloor - 1 & \text{if } v \equiv 7 \text{ or } 10 \pmod{12}, \\
\lfloor \frac{v}{4} \lfloor \frac{v-1}{3} \rfloor\rfloor & \text{otherwise}. \end{cases}
$$
The maximal number of groups when there are $v$ players, denoted $D(2,4,v)$, is equal to $J(2,4,v)$ unless $v \in \{9,10,17\}$, in which case $D(2,4,v) = J(2,4,v)-1$, and unless $v \in \{8,11,19\}$, in which case $D(2,4,v) = J(2,4,v)-2$.
The more general case in which every pair can appear at most $\lambda$ times has been solved by Assaf in his paper The packing of pairs by quadruples.
Context
StackExchange Computer Science Q#67832, answer score: 6
Revisions (0)
No revisions yet.