COMS 482: unofficial class blog

• Source s with outflow only
• Source t with inflow only
• Directed graph with non-negative edge capacities

The goal is the minimize the flow from s -> t. A flow is a function f:E -> R+, from the edge set to amount of flow on that edge. We also define c_e to be the capacity of an edge e. To be a legal flow:

1. For each edge, 0 <= f(e) <= c_e
2. For each node v other than s, t, fⁱⁿ(v) = f^out(v)

The value of a flow f, v(f) = fⁱⁿ(t) = f^out(s) = sum( f(e) ) of e_out of s = sum( f(e) ) of e_in of t. As you’ve seen by now, fⁱⁿ(v) = sum( f(e) ) of e_in of v, and f^out(v) = sum( f(e) ) of e_out of v.

Here is an example of a network flow diagram:

Now, imagine pushing 18 units of flow across nodes {s, 1, 3, 4, t} to get the following flow diagram:

This is bad–it uses up too much of our capacity. The most we can push again from s -> t is only 2! Let’s allow the option of “undoing” an edge:

This is our redidual graph. Everywhere we have flow, we potentially have:

1. Some capacity left
2. Some “backflow” we can use to change our mind

Ford-Fulkerson Algorithm (Overview):

Find an s -> t path in graph
Update all flows
Make a new residual graph
Repeat