Chapter 7.5: The Bipartite Matching Problem

A bipartite graph G=(V,E) is an undirected graph whose node set can be partitioned as V=X∪Y with the property that every edge e in E has one end in X and the other end in Y. A matching M in G is a subset of the edges M⊆E such that each node appears in at most one edge in M. The Bipartite Matching Problem (BMP) is that of finding a matching in G of largest possible size.

Beginning with the graph G in an instance of the BMP, we construct a flow network G'. First we direct all edges in G from X to Y. We then add a node s and an edge (s,X) from s to each node in X. Then we add a node t and an edge (Y,t) from each node in Y to t. Each edge in G' has capacity 1. Computing the value of the maximum s-t flow in G' is equal to the size of the maximum matching in G. We can use the flow itself to recover the matching.

Suppose there is a matching in G consisting of k edges. So there is a flow f' in G' of value k. We know that there is an integer-valued flow f of value k and since all capacities are 1, this means that f(e) is equal to either 0 or 1 for each edge e. Now, consider the set M' of edges of the form (x,y) on which the flow value is 1. We know:

1. M' contains k edges
2. Each node in X is the tail of at most one edge in M'
3. Each node in Y is the head of at most one edge in M'

The size of the maximum matching in G is equal to the value of the maximum flow in G' and the edges in such a matching in G are the edges that carry flow from X to Y in G'.

This algorithm runs in O(mn) time.

I would rate this section a 6. I understand all of it, except the part about perfect matchings. I think I will have to wait and see what the lecture slides for this section look like, because right now I have no idea of what's going on with that stuff. Other than that, this section was way better than 7.2!!