Chapter 7: Network Flow

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.

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.