# How to find n-1 complete matches for bipartite graphs that are related (speed-date)?

How can one assign n people pairwise to n-1 tables, in a speed-date fashion, such that no two persons meet twice and each person is at each table exactly once? Does this problem have a name?

### The problem in full

Given n people (n is even), assign them in pairs in n-1 rounds. Each round represent a list of n/2 pairs, each pair being two individuals that have not met earlier.

For each round, find a match between the n/2 pairs and n-1 tables, so that every pair are assigned a table. The tables are unique. Through all n-1 rounds, an individual should meet each other individual exactly once, and be at each table exactly once.

### What have I tried?

Here is the naive bipartite matching algorithm I've created so far:

1. Create rounds using the round-robin tournament scheduling.
2. Represent each round as a bipartite graph, pairs vs tables.
3. For each round, find a match.
• For each player, remove table matched in this round.

In pseudo:

n = 6
tables = [1, 2, 3, 4, 5]
players = [{'i': 1, 'tables': copy(tables)}, {'i': 2, 'tables': copy(tables), ...]
rounds = roundRobin(players)
# each round has a list of pairs
# each pair is two players
# [
#     [[1,6], [2,5], [3,4]],
#     [[1,2], [3,6], [4,5]],
#     ...
# ]
matches = []
# keep matches

for round in rounds:
match = hopcroft_karp(round, tables)
# pair 1 to table 1, ...
# [ [1, 1], [2, 2], [3, 3] ]

if len(match) !== len(round):
# TODO: backtrack
else:
for edge in match:
pair = round[edge]
table = edge
removeTable(pair, table)
removeTable(pair, table)


### Example

For some n, there is no solution. For example n = 4. I'm unsure for which n the problem has solutions. Here is n = 4 as an example:

People: 1, 2, 3, 4
Tables: A, B, C

Round 1: A:1,2 - B:3,4
In round 1, we can assign tables at random, because
the problem is the same with renaming tables.
Round 2: C:1,3 - ?:4,2 <-- not possible
4 has already been at table B.
2 has already been at table A.
Table C is taken by pair 1,3.
Round 3: ?:1,4 - ?:2,3 <-- same as round 2

• Thanks for your feedback. I've edited the question, hope it's more clear now. What I want answered is in the top. Mainly, how to solve the problem. I think the main obstacle lies in the backtracking, maybe creating a data-structure that allows that. If not, my take and the pseudo code can probably be discarded. – arve0 Sep 23 '17 at 18:55
• I have no idea what you're asking. Can you give an example of a legal schedule for various values of $n$? – Yuval Filmus Sep 24 '17 at 7:39
• @YuvalFilmus I've added an example, which has no solution, but should shed light on what is the problem. Finding a legal schedule is the problem, so I do not have any legal schedules as of now. If anything else is unclear, please let me know. – arve0 Sep 24 '17 at 9:28

Your problem seems to be the same as that of constructing a Room square. Let me quote from The existence of Room squares by Mullin and Wallis:

A Room square of side $2n+1$ is a $2n+1$ by $2n+1$ array of cells and a set $S$ of $2n+2$ objects called symbols which satisfy the following conditions:

(i) Every cell of the array is either empty or contains an unordered pair of distinct symbols from $S$.

(ii) Each symbol occurs in every row and column of the array.

(iii) Every unordered pair of symbols occurs precisely once in the array.

Mullin and Wallis state that a Room square of size $v$ exists for all odd positive $v$ except for $v=3,5$. This explains why your construction for $n=4$ (which corresponds to $v=3$) wasn't successful.

To construct a Room square, look into the article Construction of Room Squares by Stanton and Mullin.

• I've not yet been able to generate a patterned starter, as I haven't grokked the paper. But I've created a package which generates Room Squares from k=7 to k=47 by using the starters found in the paper. npmjs.com/package/room-squares – arve0 Sep 26 '17 at 17:44