Chapter 7.1: The Maximum Flow Problem and the Ford-Fulkerson Algorithm

Graphs are often used to model transportation networks; networks whose edges carry some sort of traffic and whose nodes act as switches, passing traffic between edges. Network models of this type have capacities on the edges, indicating how much they can carry, source nodes in the graph, which generate traffic, sink nodes which can absorb traffic as it arrives, and the traffic itself, which is transmitted across the edges. A flow network is a directed graph G=(V,E) with the following features:

• each edge has an associated capacity, which is a nonnegative number that we will denote c_e
• there is a single source node s in V
• there is a single sink node t in V

nodes other than s and t will be called internal nodes

We will assume that no edge enters the source s and no edge leaves the sink t, that there is at least one edge incident to each node, and that all capacities are integers.

We say that an s-t flow is a function f that maps each edge to a nonnegative real number. The value f(e) intuitively represents the amount of flow carried by e. A flow f must satisfy the following two properties:

• for each e in E, 0 ≤ f(e) ≤ c_e
• for each node v other than s and t, the sum of all flow going into v is equal to the sum of all flow going out of v

Given a flow network, a natural goal is to arrange the traffic so as to make as efficient use as possible of the available capacity. So, the basic algorithm we consider will be: given a flow network, find a flow of maximum possible value.

Suppose we divide the nodes of the graph into two set, A and B, so that s is in A and t is in B. Then, any flow that goes from s to t must cross from A into B at some point and thereby use up some of the edge capacity from A to B. This suggests that each “cut” of the graph puts a bound on the maximum possible flow value. Our algorithm is intertwined with a proof that the maximum-flow value equals the minimum capacity of any such division, called the minimum cut.

Both dynamic programming and greedy algorithms fail to produce a result of maximum flow so we have to try something else. What we can do is push forward on edges with leftover capacity and push backward on edges that are already carrying flow, to divert it in a different direction. A residual graph provides a systematic way to search for forward-backward operations such as this. Given a flow network G, and a flow f on G, we define the residual graph G_f of G with respect to f as follows:

• the node set of G_f is the same as that of G
• for each edge e=(u,v) of G on which f(e)<c_e, there are c_e-f(e) “leftover” units of capacity on which we could try pushing flow forward. So we include the edge e=(u,v) in G_f, with a capacity of c_e-f(e). We will call edges included this way forward edges
• For each edges e=(u,v) of G on which f(e)>0, there are f(e) units of flow that we can “undo” if we want to, by pushing flow backward. So we include the edge e'=(u,v) in G_f, with a capacity of f(e), in the opposite direction as e=(u,v). We will call these edges backward edges

Let P be a simple s-t path in G_f. We define bottleneck(P,f) to be the minimum residual capacity of any edge on P, with respect to the flow f. augment(f,P):

• Let b=bottleneck(P,f)
• for each edge (u,v) in P:
• if e=(u,v) is a forward edge then increase f(e) in G by b
• else decrease f(e) in G by b

return f

The result of augment(f,P) is a new flow f' in G, obtained by increasing and decreasing the flow values on edges of P.

max-flow:

• f(e)=0 for all e in G
• While there is an s-t path in the residual graph G_f
• let P be a simple s-t path in G_f
• f'=augment(f,P)
• update f to be f'
• update the residual graph G_f to be G_f'

return f

This algorithm runs in O(mC) time where C is the sum of all capacities in G and m is the number of edges in G.

I would rate this section a 5. This is a really difficult concept to wrap my head around. I wish there were more pictures or diagrams or examples. I think the lecture slides will prove to be more helpful.