Chapter 7: Network Flow

Essentially a return to bipartite matching, this chapter extends the special case of the Bipartite Matching Problem to other matching problems such as the mapping of customers to stores. We recall the definitions of matching and perfect matching, which are, respectively, “collections of pairs over a set,” and a matching for which “every node appears in exactly one edge.” We will construct polynomial algorithms to solves these problems.

Set-up: Explains the terminology for flow problems. Describes the two conditions that define flow (capacity and conservation). The structure of a flow network determines its maximum value (value = flow generated at source) of a flow.

Problem outline: Find a maximum flow in a network. Sometimes single s-t paths don't support maximum flow…in these cases we might want to “push forward” on edges with residual capacity, or “push backward” on edges that already have some flow. The point of this augmentation is to divert flow so that more flow can be added to the network without violating conditions. This leads to residual graphs, which look like network graphs but define new capacities (called residual capacities) which are the old capacities minus the current flows through that edge.

Solution: Function that augments the flow by making use of the various forward edges and backward edges in the residual graph. The Ford-Fulkerson Algorithm, as it's called, builds up the solution from zero flow to maximum flow by augmenting and updating the residual graph until there are no more s-t paths in it. The running time O(mC) because the bound on the number of edges in the residual graph is O(m), and the algorithm can run in at most O(C) iterations, where C is the sum of the capacities out of the source node.