Skip to main content

Max Flow and Ford-Fulkerson

What This Concept Is​

A flow network is a directed graph G = (V, E) with nonnegative edge capacities c(u, v) >= 0, a distinguished source s, and a distinguished sink t. A flow f is an assignment of real numbers to edges satisfying:

  • Capacity. 0 <= f(u, v) <= c(u, v) for every edge.
  • Conservation. For every v != s, t, sum over u f(u, v) = sum over w f(v, w) - what flows in equals what flows out.

The value of the flow is the net flow leaving s:

|f| = sum over v f(s, v) - sum over v f(v, s)

The max-flow problem asks for a flow of maximum value.

The Ford-Fulkerson method is the template:

f := 0 on every edge
while there exists an augmenting path P from s to t in the residual graph G_f:
    delta := min residual capacity along P
    push delta units of flow along P
return f

The residual graph G_f has, for each edge (u, v) with f(u, v) < c(u, v), a forward residual edge of capacity c(u, v) - f(u, v), and for each edge with f(u, v) > 0, a backward residual edge of capacity f(u, v). Backward edges allow the algorithm to "undo" a bad decision.

Ford-Fulkerson is a method rather than an algorithm because the choice of augmenting path is unspecified. Different choices yield different concrete algorithms (Edmonds-Karp, Dinic, capacity scaling) with different complexity bounds.

Why It Matters Here​

Max flow unifies a surprisingly large family of problems under one algorithmic umbrella:

  • bipartite matching (concept 20)
  • project / task selection with prerequisite structure (min-cut formulations)
  • edge-disjoint and vertex-disjoint paths (Menger's theorem)
  • image segmentation with data and smoothness terms (graph cuts in vision)
  • baseball elimination (Hoffman 1974)
  • survey design, scheduling, and routing with capacities
  • the LP dual of min-cut - gateway to linear programming (covered in Module 5)

If you can build the right flow network, you inherit decades of algorithmic progress.

Concrete Example​

Network:

Ford-Fulkerson might first find s -> a -> t with bottleneck 4: push 4. Residual now has c(a, t) = 0, backward t -> a with 4.

stepaugmenting pathbottleneckflow after
1s-a-t44
2s-b-c-t913
3s-a-c-tmin(6, 8, 1) = 114
4s-b-?none (b-c saturated, no forward path)terminate

Max flow = 14. The min cut {s, a, b, c} vs {t} has capacity c(a,t) + c(c,t) = 4 + 10 = 14, confirming the max-flow/min-cut equality.

Common Confusion / Misconceptions​

  • "Backward edges look like edges that weren't in the graph." They are residual edges; they encode the ability to cancel previously pushed flow. Without them, a greedy choice on an early augmenting path can permanently block the optimal routing.
  • "Ford-Fulkerson is polynomial." No: with adversarial augmenting path choices, it can take O(|f*|) iterations where |f*| is the max-flow value - exponential in input size if capacities are large, and non-terminating for irrational capacities.
  • "Only integer capacities make sense." Rational capacities work (scale to integers). Irrational capacities can break termination of the method; this is why Edmonds-Karp or capacity scaling is preferred in theory.
  • "Max flow and min cost flow are the same problem." No - min cost max flow adds per-edge costs and asks for the cheapest max flow; solved via successive shortest paths or cycle-cancelling, not plain Ford-Fulkerson.
  • "Multiple sources/sinks require a new algorithm." Add a super-source connecting to all real sources with infinite capacity; same for sinks.

How To Use It​

Implementation skeleton with explicit residuals:

for each edge (u, v, c): 
    add forward (u, v, c) and backward (v, u, 0), 
    cross-link them as reverse pointers
while BFS/DFS finds a path P from s to t using residual edges with capacity > 0:
    delta := min residual capacity along P
    for each edge e on P:
        e.cap := e.cap - delta
        e.reverse.cap := e.reverse.cap + delta
    total := total + delta
return total

Integration checklist:

  1. represent every edge with a pointer/index to its reverse so pushing flow updates both sides in O(1)
  2. treat undirected edges as two directed edges with capacity c each (not one with c and one with 0)
  3. add super-source and super-sink for multi-source/multi-sink problems
  4. model vertex capacities by splitting each vertex v into v_in and v_out with capacity equal to the vertex constraint
  5. always pick BFS or some structured rule for augmenting paths in practice - this is Edmonds-Karp and guarantees polynomial time

Transfer / Where This Shows Up Later​

  • S3 (systems). Bandwidth allocation in data center networks, CDN cache placement, container scheduling with resource caps.
  • S4 (compilers). Register allocation via min-cut formulations, certain optimization problems on program-dependence graphs.
  • S5 (OS). I/O scheduling with device throughput constraints, network QoS models.
  • S6 (databases). Query optimization via flow-based cost models, transaction scheduling with conflict flows, partitioning for joint storage.
  • S7 (DDD). Capacity planning across bounded contexts, identifying bottleneck integration points via min-cuts of dependency graphs.
  • S8 (distributed). Bandwidth routing, multi-commodity flow approximations for traffic engineering, replica placement under capacity constraints.

Back-link to concept 09 (shortest-path variants) because BFS-based augmenting paths reuse the same infrastructure, and forward to concepts 18, 19, 20 for faster variants and applications.

Check Yourself​

  1. Why are backward residual edges necessary, and what role do they play in "undoing" decisions?
  2. Why is naive Ford-Fulkerson not polynomial in |V| and |E| alone?
  3. How does the algorithm terminate on integer capacities?
  4. What is the value of the flow equal to at termination, and why (hint: max-flow min-cut)?
  5. Transform a multi-source, multi-sink problem into a single-source, single-sink one; what invariant must your super-edges satisfy?
  6. Give a vertex-capacity example and show the vertex-splitting transformation.

Mini Drill or Application​

On the network

s -(3)-> a, s -(2)-> b
a -(1)-> b, a -(3)-> c
b -(2)-> c, b -(3)-> t
c -(2)-> t

run Ford-Fulkerson by hand. Find at least two distinct execution paths (different augmenting-path sequences) that lead to the same max-flow value. Verify the max-flow value by identifying a matching min-cut.

Implementation drills.

  1. Implement Ford-Fulkerson with explicit residual edges using an adjacency list of Edge records with rev indices.
  2. Build a small test suite: single edge, chain, diamond, and a 10-vertex random network; compare your output against a reference (NetworkX maximum_flow).
  3. Transform a bipartite matching instance into a max-flow instance and solve it.
  4. Model a project selection problem (each project has a profit; each prerequisite costs c_i) as max-flow / min-cut.
  5. Try two pathological instances where DFS-based augmentation explodes in iterations - see why Edmonds-Karp is the default in practice.

Read This Only If Stuck​