Bipartite Matching And Max Flow – Tweaks And Other Observations

When I was in Dr. Frederickson’s CS 381 class (if you go to Purdue CS and are wondering if you should sit in his CS 381, I would say YES), I learned how to solve a simple class of Matching problems, biparitite matching.

So, you have 2 sets of vertices and no 2 members of the same set are connected. Now, given a bipartite graph, we are supposed to find a maximum matching for it.

The simplest way to solve this problem would be to use integer valued flow. Here’s our sample graph:

Well, the obvious solution is to direct the edges from the set on the left (marked L in the pic below) to the set on the right (marked R in the pic below) and to make a source vertex and a sink vertex. Next, to apply integer valued flow algorithms on this network, set the capacity of each edge to 1.

PS, I haven’t noted the capacities in the graph above because that would introduce too much clutter. But the capacities are indeed 1. When you run any method on this network that computes maximum integer valued flow (Choose between Ford-Fulkerson and Edmonds-Karp), you are going to have a flow of 0 or 1 on the edges in the graph. The edges that have flow = 1 on them are the ones that are included in the matching and those that are not in the matching have a flow value = 0. Here is one of the possible matchings:

The edges that are untouched have a flow value = 1 (also equal to the capacity of the edge) and those that look like they’ve been shot (i.e have holes in them, have a flow of 0 and hence are not in the matching).

Well, everyone knows this stuff. Else you wouldn’t have approached this line is < 10 seconds. Anyway, in one very productive office hour session with Dr. Frederickson, he pointed out the importance of using an approach to solve a problem. In this case, why do we set a capacity of 1 and compute max integer-valued flow? Well, considering I have a really low IQ, I had to look at this problem as if it were a communication network. Setting a capacity of 1 on each edge and then computing max flow would give us edges with a flow value of 1 or 0. That means we either use the edge to communicate or we don’t (this is why we set a capacity of 1).

So, extending this thinking to problems that bipartite matching can solve, let us consider the simple problem:

B is a set of boys who need to be paired up with girls in set G. Any boy can be paired with any girl.

So, the solution would involve what we just did.

Now, we can modify the problem so:

B is a set of boys who need to be paired up with girls in set G for a performance at their community center. Each boy can appear at most thrice and each girl can appear at most 4 times and a pair can appear at most twice.

Extending my “communication network” idea, this problem can also be solved by computing a max flow on this network. But we need to set the capacities on each edge correctly.

• We have an edge from a source S to every boy. Now, a boy can appear at most thrice. This essentially means, the boy can be picked once, twice, three times (or if he really sucks, he might not be picked at all). So, the capacity you set on this edge is 3.
• Now, we have an edge from every girl to a sink T. Remember a girl can be picked at most 4 times. So, the capacity of the edge from every girl to the sink is 4.
• Now, each pair can appear twice so every edge from set B to set G gets a capacity of 2.

That’s it. Computing max flow on this should give us a decent matching!