We will begin with two basic applications: first, the Bipartite Matching Problem and the Disjoint Paths Problem in the next section. The Problem. A bipartite graph is an undirected graph whose node set can be partitioned as V=XUY, with every edge in the graph joining a node from X and one from Y. Designing the Algorithm. The graph defining a matching problem is undirected, while flow networks are directed; but its actually not difficult to use an algorithm for the Maximum-Flow prpblem in this case. we first construct a flow network G' from G and give each edge a capacity of 1. We now compute a maximum s-t flow in this network G'. The value of this maximum is equal to the size of the maximum matching in G. Analyzing the Algorithm. The analysis is based on showing that integer-valued flows in G' encode matchings in G in a fairly transparent fashion. Suppose there is a matching in G consisting of k edges. Then, consider the flow f that sends one unit along each path. One can verify that the capacity and conservation conditions are met and that f is an s-t flow of value k. By the integrality theorem for maixmum flows, we know 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 for M', a set of edges of the form(x,y) on which the flow value is 1, M' has the following properties:
- M' contains k edges
- Each node in X is the tail of at most one edge in M'
- 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'.
Running Time. let m be the number of edges and n=|X|=|Y|. We assume there is at least one edge incident to each node in the original problem and hence m>=n/2. The Ford-Fulkerson Algorithm can be used to find a maximum matching in a bipartite graph in O(mn) time.
Extensions(The Structure of Bipartite Graphs with No Perfect Matching). Not all bipartite graphs have perfect matchings. What does a bipartite graph without a perfect matching look like? It would be nice if the algorithm, upon concluding that there is no perfect matching, could produce a short “certificate” of this fact. The certificate could allow someone to be quickly convinced that there is no perfect matching, without having to look over the whole execution of the algorithm. One way to understand the idea of such a certificate is, a graph G has a perfect matching by checking if the maximum flow in a related graph G' has value at least n. But we want the certificate to appear natural to us, thus, we might want to consider finding any two edges that have only one incident edge each, and the other end of each edge is the same node. If a graph has a perfect matching, then each node in A has to be matched to a different node in the other subset of Y. A perfect matching or an appropriate subset can be found in O(mn) time.
This section was new, but not conceptually difficult, I give it an 8.5/10.
