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

We will be looking at transportation networks - networks whose edges carry some sort of traffic and whose nodes act as “switches” passing traffic between different 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 “absorb traffic” as it arrives; and the traffic, or flow, which is transmitted across the edges.

Flow Networks

A flow network is a directed graph with the following features

• Associated with each edge e is a capacity. Ce.
• There is a single source node s
• There is a single sink node t
• Nodes other than s and t are called internal nodes.

The flow on an edge cannot exceed the capacity of the edge.

The Maximum-flow Problem

Given a flow network, we will look to find the MAX flow possible. The maximum-flow value equals the minimum capacity of the minimum cut. This minimum cut follows the idea that we can divide the nodes of the graph into two sets, A and B, so that s is in A and t is in B. Any flow that goes from s to t must cross from A to B, and thereby use up some of the edge capacity from A to B.

Designing the Algorithm

We can push flow forward on edges with leftover capacity, and backward on edges that are already carrying flow, to divert it into a different location. This is better shown in the residual graph which provides a systematic waay to search for forward-backward operations.

Let P be a single s-t path in the graph G –> P does not visit any node more than once. bottleneck(P, f) is 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
      increase f(e) in G by b
    Else ((u,v) is a backward edge, and let e = (v,u))
      decrease f(e) in G by b
      
  return f

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

Max-Flow
  Initially f(e) = 0 for all e in G
  While there is an s-t path in the residual graph Gf
    Let P be a simple s-t path in Gf
    f' = augment(f, P)
    f = f'
    Update the residual graph Gf to Gf'
    
  return f

This is called the Ford-Fulkerson Algorithm. It can be implemented to run in O(mC) time, in which m is the number of edges in G, and C is the maximum capacity out of the source node s.

This chapter is very interesting, Ford and Fulkerson must have been some smart guys. 9/10.