In class we have discussed various algorithms that require the ability to find a perfect matching in a bipartite graph efficiently. For example, each step of the market-clearing price algorithm asks the question “is there a perfect matching”? Similarly, the Vickrey-Clarke-Groves algorithm also requires the computation of a perfect matching in each step.
A major problem encountered in computer science is the efficiency of algorithms. A natural question one may ask is “What does it mean for an algorithm to be efficient?” Efficiency can have multiple meanings. It could deal with minimizing the use of resources (such as space), or it could deal with minimizing the time taken for the algorithm to run. In this post, we shall be considering the latter.
Lets take consider the market clearing price algorithm. Assume that the number of buyers and sellers is n (i.e. they are the same, since otherwise, a perfect matching would not be possible). The total number of edges between each individual buyer and seller is m. One solution to finding a perfect matching could try out every possible combination of edges. If an edge set satisfying a perfect matching is found, then we have a perfect matching. Otherwise we do not. However, it is not too hard to see that the number of possible combinations of edges is 2m (think of each edge having 2 choices: it either belongs to the set or it does not. Since we have m edges, we have 2m choices).
This means that if there is no perfect matching, we would have to take 2m steps to realize this. With small values of m, this is not a huge problem. However, once m gets larger, the number of possible combinations of edges increases exponentially. Clearly, with large values of m, this algorithm would take exponentially long to run and we would have to wait really long each time we need to check the graph for a perfect matching.
Thus, the question now is: Is there more reasonably efficient way to find a perfect matching in a bipartite graph? To solve this problem, we can use a class of algorithms known as network flow algorithms. The following is the idea behind how flow networks work: Imagine a series of pipes carrying water. Each pipe has a certain capacity and so the amount of water flowing through it cannot exceed its capacity. Pipes are also connected to other pipes at certain points to give rise to new pipes. At these points, the amount of water flowing into the new pipe has to be the same as the total water flowing out of the old ones. We also need to have a source of water and a sink that are connected to certain pipes. The source generates all the water, while the sink absorbs all the water. A flow can then be considered to be one way of transferring water from the source to the sink, while ensuring that the conditions above are met. The idea behind many network flow algorithms is to figure out a way to maximize the amount of flow in such a system.

The bipartite graph in figure 1 can then be converted into the equivalent flow network in figure 2, where we can set each edge to have a capacity of 1 unit. We can then run a maximum flow algorithm such as the Ford-Fulkerson algorithm on the graph. The algorithm will essentially push flow out of the source, while maintaining the flow conservation conditions. As we can see, the maximum possible flow can have a value of at most n (since only 1 unit can flow out from each edge connected to the source). Also, if the flow returned by the algorithm has a value less than n, we know that a perfect matching does not exist. If the flow returned equals n, then the perfect matching exists and can easily be obtained from the new graph. It can be shown that this algorithm can take a maximum of mn steps, thereby making it considerably faster than the algorithm discussed earlier.