In this chapter, we discuss network flow algorithms.
We can use graphs to model flow networks. In these networks, edges have certain capacities that indicate the maximum flow allowed over that edge and nodes represent interchanges that direct the flow to some edge. A source node (s) generates flow, a sink node (t) absorbs it, and all other nodes redirect the flow so that the amount of flow into it is the same as the flow out. We want to find the maximum possible flow we can send through the network.
We can do this using the Ford-Fulkerson algorithm. First we need to create a residual graph. This looks identical to our original graph initially. As we add flow, we decrease the capacity of the original edge (say from u to v) and add a backward edge (from v to u) with capacity equal to the amount of flow currently flowing from u to v. When an edge is at capacity, i.e. the remaining capacity is zero, we remove it from our residual graph, leaving just a backward edge. We need this residual graph with backward edges so that we can undo flow we may not want on a certain edge.
Now we are ready to run the algorithm. We are looking to maximize flow, so we begin with no flow and find an s to t path we can augment in the residual graph. We identify the bottleneck b (capacity of edge of minimum capacity) of this path and then check the edges in the path. If all of the edges were in the original graph, then we can add a flow of b to each edge. If any of the edges were not in the original graph, we still add a flow of b to edges that were in the initial graph but we instead remove a flow of b from those edges that are backward edges. This undoes some of the flow from that edge and pushes it along a different path. When no more paths exist, we are done. (p 344)
We can implement this algorithm in O(mC) time, where m is the number of edges and C is the maximum flow we could send out of the source node s.
Readability: 8
It is not immediately obvious that the Ford Fulkerson algorithm actually gives us the maximum flow. We will show this by looking at s-t cuts. We will say A is the set containing s and B is the set containing t. The capacity of the cut is the sum of the edges out of A. First we note that the value of the flow in the network is the value of the flow out of A minus the flow that comes back into A. Then we note this flow must be less than or equal to the capacity of any given cut since the flow must travel from s to t. Now if the flow returned by the Ford Fulkerson algorithm is f, we can show it is the maximum. Since the algorithm stops when there are no more paths from s to t in the residual graph, there is an obvious cut where A is the set of nodes reachable from s in the residual graph. In this case, the flow out of the cut must be f and the capacity of the cut is f as well since all of the edges out of it are completely saturated. This automatically tells us the flow we have is the maximum flow, since it cannot be larger. It also tells us this is the cut of minimum capacity, since if there was a cut of lower capacity, we could not have found a flow higher than that capacity. That is, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut.
Note that if we did not have integer capacities the FF algorithm would not necessarily terminate, but the max flow - min cut theorem still holds.
Readability: 8
In this section, we see how to solve the bipartite matching problem using our new algorithm. First we need to create a flow network from our original graph. This network will have directed edges from nodes in X to nodes in Y, in place of any undirected edge between a node in X and a node in Y. Then we add a source node with an edge from it to each node in X, and a sink node with an edge to it from each node in Y. Each edge has capacity 1. Finally we run the FF algorithm. This gives us the size of the maximum matching (since the capacities are 1, each node can appear at most once). We can then use the flow to find the matching. We can find this matching in O(mn) time.
Readability: 8
We can also use our algorithm in other more complex problems. Suppose we want to solve a circulation problem. In this problem, we have supplier nodes and demand nodes. We want to satisfy the demand by moving the flow from suppliers to demand nodes. We can also have flow move through these nodes, but suppliers ultimately want to supply and demand nodes want to receive. We can apply our algorithm to solve this problem by slightly modifying the existing graph. We attach a single source node that points to all the suppliers and a single sink that all the demand nodes point to and then run the FF algorithm. This will return the maximum flow. If this maximum flow is the same as the total supply, then we can remove the source and sink and be left with a circulation. Otherwise, a circulation does not exist.
Networks can also have lower bounds for edges that require a certain flow. Suppose we have a circulation problem with lower bounds. Then we can just reduce the maximum capacity of each edge by the lower bound and reduce the demand of each node by L = lower bound of edge in - lower bound of edge out. Now we have a network without lower bounds and the idea above can be applied.
Readability: 8