# Reducing a seating problem to maximum flow

Problem:
We have p different families with $$1 \leq i \leq p$$ members for the $$i$$-th family. We also have q tables where table $$t_j$$ has a capacity of $$1 \leq j \leq q$$. We want no two members of a family sitting on the same table.

I need to reduce this to a maximum flow problem and came up with the following idea:

We have a source node which is connected to every family. The flow between the source and a family is the number of members the family has. On the right side we have the destination source which is connected to every table and has a flow of the table capacity.

But now I am unsure, how to properly connect the families and tables. My idea is, that every family has a connection to every table but I am unsure what the flow capacity would be there.

Any help would be appreciated.

Create vertices

• $$s$$, $$t$$
• $$f_1, f_2, ..., f_n$$ for each of the $$n$$ families.
• $$t_1, t_2, ..., t_m$$ for each of the $$m$$ tables.

Create edges

• from $$s$$ to $$f_i$$ with capacity the size of the $$i$$th family.
• from $$f_i$$ to $$t_j$$ with unit capacity
• from $$t_j$$ to $$t$$ with the capacity the size of the table.

This ensures that each family sends at most one person to each table, and that each table gets at most its capacity many guests.