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:

bipartite_matching

 

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s