maximum bipartite matching (ford-fulkerson)

Question

I was reading http://www.geeksforgeeks.org/maximum-bipartite-matching/ and http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm and am having trouble understanding. It seems the example is under the assumptions that each job can only accept 1 person and each person wants 1 job. I was wondering how the algorithm/code would change if for example, the v set had capacity > 1 (can hire multiple people for that job) and the u set > 1 (each person wants more than 1 job)?

Overrefinement

You just have edge capacities > 1 on the left and right side of the graph and find the maximum flow as usual. Your algorithm needs to be a bit more general to keep track of the bottleneck capacity of the augmenting path. You can read about Ford-Fulkerson on Wikipedia – Stacee

So let's say each person wants exactly 2 jobs and each job has 3 spots available. Would the graph look like this? i.imgur.com/B0SvQjU.png – Overrefinement

The edges in the middle should have capacity 1, unless you want to assign a person to the same job multiple times (which might be sensible depending on your use case). Then you find the max-flow in that graph and check whether it is equal to 8 (sum of capacities on the left side). If not then you can't fulfill every need for a job – Stacee

Answer 1

To allow jobs to have more than one person assigned to them, you'd only modify edge capacities from Jobs to Terminal (Similar to how Niklas B. described in his comment, but not exactly.)

Like this:

The capacities of 1 from the Source to the People, and 1 from People to Jobs guarantees that a person will only ever be selected for one job (because the maximum flow that they can contribute overall is 1). However, the capacities > 1 from Jobs to Terminal allows that more than one person can be assigned to that job.

If a person can perform also more than 1 job, then the max flow from Source to Person increases by that amount:

Where i, j, k, and x are stand-ins for integers with values >= 1

The key thing to remember here is that flow capacities to the left of People dictate how many jobs they may take, and the flow capacities to the right of Jobs dictate how many people may be assigned that job. The capacities in the middle should not change.

Mcfarland