Maximum Matchings in Bipartite Graphs

Maximum matchings can be found algorithmically in any graph in polynomial timeThe running time is a polynomial in n and m, where n is the number of vertices and m is the number of edges in the graph.. However, in this course, we restrict our attention to the simpler problem of finding a maximum matching in bipartite graphs.

In fact, it can be a little astonishing to learn that the Ford-Fulkerson algorithm can also be used for finding a maximum matching in a bipartite graph!

The central idea is to use the Ford-Fulkerson algorithm

The basic idea is to first systematically convert a bipartite graph into a flow network and then find a maximum flow in the network using the Ford-Fulkerson algorithm. The network is constructed in such a way that the flow through the edges can be used for finding a maximum matching in the original graph.

Conversion to a flow network

Suppose $G$ is a bipartite graph with partite sets $L$ and $R$. $G$ can be converted into a flow network by making the following modifications to it:

1. Assign directions to all edges in $G$ such that the tail vertices are in $L$ and the head vertices are in $R$.
2. Add a source vertex $s$ and a sink vertex $t$ to $G$.
3. Add an edge from the source $s$ to each vertex in $L$. Also, add an edge from each vertex in $R$ to the sink $t$.
4. Set the capacity of each edge as $1$

...