7.15
The guests and their feuds form an undirected graph G = (V,E) where each vertex is a guest and an edge connects two guests on bad terms. Finding two tables with no feuding pair is exactly the problem of deciding whether G is bipartite and, if so, outputting its two color classes.
Algorithm (BFS-based 2-coloring)
function two_tables(G):
color = { } # guest → 0 / 1 (table number)
for each guest s in V:
if s ∉ color: # new component
color[s] = 0
queue = [s]
while queue:
g = queue.pop(0)
for each neighbor h of g: # all guests g dislikes
if h ∉ color:
color[h] = 1 - color[g]
queue.append(h)
elif color[h] == color[g]:
return "IMPOSSIBLE" # odd cycle → not bipartite
T0 = { g | color[g] = 0 }
T1 = { g | color[g] = 1 }
return (T0, T1)
Correctness• The BFS explores every connected component; the first time it sees a vertex it assigns it the opposite color of the vertex it was reached from. Hence every edge joins vertices of different colors.
• If an edge is found whose endpoints already share the same color, the graph contains an odd cycle, proving that no 2-table assignment can avoid a feuding pair.
• Conversely, if the algorithm finishes without conflict it produces a partition (T0,T1) where each edge spans the two sets, so no feuding pair shares a table.
Complexity
Each vertex and edge is processed once: O(|V| + |E|) time and O(|V|) space.
Thus the procedure above efficiently returns either two compatible guest lists—one for each table—or reports that no such seating arrangement exists.
Back to
Chapter 7
