[Solved]: Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Problem Detail: 

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a marriage can be set up among the corresponding man and women.

Each broker $i$ can set up a maximum of $b_i$ marriages and a person can only be married once. Also we assume all marriages are heterosexual.

I want to determine the maximum number of marriages possible and I want to show that the answer can be found be solving a maximum-flow problem.

What I've tried:

Make source and sink nodes with opposite demand. And then for each ordered pair $(i,j)$ where $i$ is a woman and $j$ is a man making a node. For each broker $j$ make a corresponding node and introduce an arc with capcity $b_j$. For each node $(i,j)$ make an arc from broker $k$ with capacity $1$ if broker $k$ can arrange a marriage otherwise $0$.

However, after this I stop. I need to keep track of state, that is no person gets married twice !

Asked By : user111854

Answered By : Nicholas Mancuso

You shouldn't need to keep track of state. This can all be handled with capacity constraints over the nodes. The network can be structured as follows:

Start with the graph where one partition consists only of the "men" nodes and the other partition consists of the "women" nodes. Now, add a node for each broker $b$ and for each marriage pair $(m, w)$ on $b$'s list create two edges $(m, b)$ and $(b, w)$. Finally add a source node connected to all men and a sink node connected to all women (you can add another arc between those to simplify constraint cases if you want, but it's not necessary).

So now we have a graph, but to have a proper flow-network we need capacity constraints. For each man and women node we have a capacity constraint of 1, since they can each only marry at most one person. For the $i$th broker node, add a capacity constraint of $b_i$. This way the total number of flows (marriages) going through the broker is at most $b_i$.

Compute maximum flow over this graph and you should be good to go.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33569

 Ask a Question

 Download Related Notes/Documents