1
$\begingroup$

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: enter image description here

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.

How should we 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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.