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 !
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
