14  Ford-Fulkerson

This section describes the Ford Fulkerson framework for solving max flow.

Objectives. After learning this material, you should be able to:

• Given a flow \(f\), construct the residual graph \(G_f\) and residual capacity \(r_f\).
• Find an augmenting path and use it to augment \(f\).
• Use the above steps to run the Ford Fulkerson framework on examples.

14.1 Breaking and fixing the natural approach

Here’s a very natural algorithm that almost works:

• Find a path from \(s\) to \(t\).
• Send as much flow along that path as possible.
• Repeat until impossible.

Unfortunately, this doesn’t always work to find the max flow! We need the ability to “cancel” use of an edge and backtrack on some decisions. Luckily, it turns out that we can achieve this by pretending to send flow “backward” along that edge, which has the effect of cancelling out the forward flow. Here’s an example:

We first send 5 units of flow along the path \(s,y,x,t\). This results in the following flow.

Now, we are stuck, because there is no path from \(s\) to \(t\) along which we can send more flow. But we have not found the max flow yet. The way out is to send 3 units of flow along the path \(s,x,y,t\). Even though \((x,y)\) is not an edge in the graph, we can “send” flow along this edge by reducing the current amount of flow.

Another way to think of what happened is that we took 3 units of flow along \((y,x)\) and re-routed it to \((y,t)\). To replace that 3 units of flow at \(x\), we brought over 3 units of flow along \((s,x)\).

This idea leads to the Ford-Fulkerson framework for max-flow algorithms. First, we need to make some useful definitions in order to fully define the algorithm.

14.2 Residual capacity function and residual graph

The residual capacity function \(r_f: V \times V \to \mathbb{R}_+\) is defined as follows:

• If \((u,v) \in E\), then \(r_f(u,v) = c(u,v) - f(u,v)\). This is the amount by which we could increase the flow along this edge without breaking the capacity.
• Otherwise, if the reverse edge \((v,u) \in E\), then \(r_f(u,v) = f(v,u)\). We can “increase” the flow from \(u\) to \(v\) by decreasing the flow from \(v\) to \(u\). The current flow is \(f(v,u)\), so that is how much we can decrease it.
• If neither \((u,v)\) nor \((v,u)\) is an edge, then \(r_f(u,v) = 0\).

The residual graph \(G_f = (V, E_f)\) is a graph where there is an edge \((u,v) \in E_f\) if \(r_f(u,v) > 0\), otherwise \((u,v) \not\in E_f\). It is important that if \(r_f(u,v) = 0\), then the edge \((u,v)\) is NOT in \(E_f\). We will draw \(r_f\) as edge weights on \(G_f\), and we’ll sometimes refer to both together as the “residual graph”.

We can describe these operations more formally as follows.

residuals(G, c, f):
   # G = (V,E) is a directed graph, c is a capacity function, f is a flow
   let Ef be an empty set
   for each edge (u,v) in G:
      set rf(u,v) = c(u,v) - f(u,v)
      if rf(u,v) > 0:
         add (u,v) to Ef
      set rf(v,u) = f(u,v)
      if rf(v,u) > 0:
         add (v,u) to Ef
   return rf, (V,Ef)

Exercise 14.1 Consider the following input graph and flow. Draw the residual graph. To do so, follow these instructions:

1. For the residual capacity function, calculate the residual capacity \(r_f(u,v)\) of each edge \((u,v)\) as well as its reverse \((v,u)\).
2. For the residual graph, draw a copy of the graph’s vertices. For every pair \((u,v)\) where \(r_f(u,v) > 0\), draw an edge from \(u\) to \(v\). Label the edge with its residual capacity.
3. Important: if \(r_f(u,v) = 0\), then edge \((u,v)\) should NOT be included in the graph.

Solution.

Notice the differences between which edges are present in the residual graph, compared to the original graph:

• Even if there is an edge such as \((s,y)\) in the original graph, it may not be present in the residual graph. This happens when flow equals capacity.
• Even if an edge such as \((y,s)\) does not exist in the original graph, it may be present in the residual graph. This happens when the reverse direction \((s,y)\) has flow.
• Even though the original graph has no antiparallel edges, the residual graph can have antiparallel edges such as \((x,y)\) and \((y,x)\). This happens when the flow is greater than zero but less than capacity.

14.3 Augmenting paths

The last concept we need is an augmenting path: a path \(s=v_1,\dots,v_k=t\) from \(s\) to \(t\) in the residual graph. Note that because this is a path in the residual graph, we have that \(r_f(v_i, v_{i+1}) > 0\) for every edge along this path. In other words, we can send more flow along every edge in this path.

Algorithm 14.1 (Augmenting a flow along a path)  

augment(G, f, rf, path):
   # G is the input graph, f is a flow, rf is residual flow
   # path goes from s to t in the residual graph
   let d = min( rf(u,v) for (u,v) in path )
   for each edge (u,v) in path:
      if (u,v) in G:
         f(u,v) += d
      else:              // here, (v,u) must be in G
         f(v,u) -= d
   return f and d

Exercise 14.2 Find an augmenting path in the residual graph of the previous exercise. Then, augment the flow along the path. To do so, follow these instructions:

1. Give a path from \(s\) to \(t\) in the residual graph.
2. Give the amount we can augment, \(d\).
3. Give the updated flow \(f\) after augmenting. To do so, draw the graph and label each edge with flow/capacity.

Solution.

1. \(s,x,y,t\). Note: this is the only path.
2. The amount is \(3\). Note: \(r_f(s,x) = 4, r_f(x,y) = 5, r_f(y,t) = 3\), so the minimum is \(3\).
3. Here is the updated flow:

14.4 Ford-Fulkerson Framework

The Ford-Fulkerson Framework is the following algorithmic framework:

Algorithm 14.2  

fordfulkerson(G, c):
   # G is a directed graph, c is a capacity function
   let f(u,v) = 0 for all vertex pairs u,v
   repeat:
      let Gf and rf = residuals(G, c, f)
      find a path from s to t in Gf
      let f and d = augment(G, f, rf, path)
      if d == 0:
         return f

Notice that line 6, where we find a path, is underspecified. How do we choose the path? There turn out to be several reasonable choices for this step. Because of this, Ford-Fulkerson is called a framework rather than an algorithm. To make it an algorithm, we need to specify how to implement line 6.

Exercise 14.3 Run the Ford-Fulkerson framework on the example graph of Figure 13.1, reproduced here. You can use any method to find a path in the residual graph.

Figure 14.1

In each round, give the following things:

• The flow \(f\) (draw this on a graph, as above), and the amount \(|f|\).
• The residual flow \(r_f, G_f\), drawn as a graph (see above).
• The augmenting path you picked, the augmentation amount \(d\).

Example solution.

There are multiple possible answers, depending on the paths chosen. Here’s one.

First round:

Flow: \(|f| = 0\).

Residual flow:

Path: \(s,v,t\). Amount: \(2\).

---

Second round:

Flow: \(|f| = 2\).

Residual flow:

Path: \(s,v,x,t\). Amount: \(2\).

---

Third round:

Flow: \(|f| = 4\).

Residual flow:

Path: \(s,w,x,t\). Amount: \(3\).

Fourth round:

Flow: \(|f| = 7\).

Residual flow:

Path: \(s,w,v,x,t\). Amount: \(3\).

Fifth round:

Flow: \(|f| = 10\).

Residual flow:

Path: no path exists from \(s\) to \(t\). Stop.

Final amount of flow: \(|f| = 10\).