This chapter is about a set of problems that grow from the Bipartite Matching Problem we talked about earlier. We can use this algorithm/idea to develop a general set of problems about traffic flow on networks.

Graphs can be used to model transportation networks, which have a capacity on the edges, a source(start) node, a sink(end) node, and the traffic across the edges. A flow network is a directed graph with a capacity for each edge, c(e), and a single source and sink node. No edges go into the source and no edges go out of the sink. The flow is a function f(e) that represents the flow on each edge. The flow into a node must equal the flow out of a node and f(e) must not exceed c(e). The value of the flow v(f) is the amount of flow generated at the source. Our goal is to arrange the traffic to efficiently use the capacity. We develop the proof along with the fact that the max-flow value equals the min-capacity at any cut.

We cannot use dynamic programming because we can run out of paths before reaching the max-flow. Therefore, we need to be able to push flow forward and backwards. We do this with the residual graph, where the nodes are the same, the forward edges represent unused capacity, and backward edges represent the flow on the edge. The algorithms on pages 343-344 find the maximum flow. The idea is to look for an augmenting path the adjust the flow and capacity on each edge in the path based on the bottleneck. We know the flow value strictly increases with each augmentation, and the running time is O(mC),

This section shows that the flow we get from the Ford-Fulkerson Algorithm is the max-flow. We can use the idea of cuts to put an upper bound on the v(f). In a cut A-B, the flow is the total amount that leaves A minus the amount that comes back into A. Furthermore, we can say that the value of every flow is upper bounded by the capacity of every cut. So, if we find a cut with a capacity c, we know there cannot be a s-t flow with a value greater than c. The Ford-Fulkerson Algorithm terminates when there are no s-t paths, which is all we need to show that v(f) is the maximum.

If we have a flow of maximum value, we can find the s-t cut of the minimum capacity in O(m) time. This leads us to the Max-Flow Min-Cut Theorem, which says that in every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut. The book also notes that we assume integer capacities, because out algorithm could run forever with real numbers. This section is sort of tricky because there are lots of details and it seems more in depth than a lot of the past sections.

This section is about how to choose the augmenting paths for the Ford-Fulkerson Algorithm in order to improve the upper bound. If you keep choosing paths with a low bottleneck, it will take more augmentations than necessary to get the result. Instead we want to choose paths that have fairly large bottlenecks. We will call the scaling parameter Δ, and we will look for paths with a bottleneck of at least Δ. We will also have a new residual graph with only the edges with residual capacity of Δ. (Δ will be power of 2). The algorithm is on page 353-354.

The Scaling-Max-Flow Algorithm is basically the same as the Ford-Fulkerson Algorithm. The only difference is that the Δ helps us choose out paths better to reduce the running time. This algorithm will still return the maximum flow value. Using the scaling, we can reduce out running time to at most O(m^2 logC) time. When C is large, this is much better than O(mC). This section makes sense to me because it clears up a lot of questions I had at the beginning of this chapter about how to actually find the augmenting paths.