The Bipartite Matching Problem (Part III)

Its time to design the algorithm now. While there exist many algorithms to solve this problem today, we shall take a look at the one that makes use of the algorithm for the Maximum Flow Problem mentioned earlier to find the maximum matching. The aim of this post is to explain the algorithm. No focus is placed on ways to implement the algorithm. I’ll leave that to the reader to figure out if he/she so wishes. Like I mentioned at the start of this series, the idea is to arrive at a clearer understanding of how analysis of algorithms actually happens.

With that said, lets get down to it. If you recall, the graph defining the matching problem is undirected, while the flow networks are directed. The first step is to convert the undirected graph G (fig (a) ) , an instance of the Bipartite Matching problem into the corresponding flow network G’ (fig (b) ). Consider the figure below:

First, we direct all edges in G from L to R without loss of generality. We now add two more nodes “s” and “t”. Second we add directed edges (s,l) from s to each node in L.  Accordingly, we add directed edges (r,t) from each node in R to t. Finally, we give each edge in G’ a capacity of 1.

We now compute a maximum s-t flow in this network G’. And that’s it. We are done !

I can imagine the confusion. I remember feeling it too. Its not at all apparent that the answer that we just got is actually the answer to the problem we have been reading about. In part IV, our analysis will show that the value of this maximum flow is in fact equal to the size of the maximum matching in G. Moreover, we shall bound the running time of this algorithm.

Advertisements