Skip to main content

Edmonds-Karp, Capacity Scaling, Push-Relabel

What This Concept Is​

Ford-Fulkerson is a method, not an algorithm - it leaves open how to pick an augmenting path. Three standard choices give polynomial-time algorithms:

  • Edmonds-Karp. Always pick a shortest augmenting path (fewest edges, not smallest weight) using BFS on the residual graph. Runs in O(|V| |E|^2).
  • Capacity scaling. Keep a threshold Delta, starting at the largest power of 2 at most the max capacity. Repeatedly find augmenting paths whose bottleneck residual capacity is at least Delta, then halve Delta. Runs in O(|E|^2 log U) where U is the max capacity.
  • Push-relabel (Goldberg-Tarjan). Maintain a preflow and vertex heights; push excess toward the sink along "downhill" admissible edges; relabel a vertex when no admissible out-edge exists. The generic version runs in O(|V|^2 |E|); the highest-label variant in O(|V|^2 sqrt(|E|)); the FIFO variant in O(|V|^3).

Dinic's algorithm (not in this module's core but worth naming) uses level graphs and blocking flows for O(|V|^2 |E|), and O(|E| sqrt(|V|)) on unit-capacity graphs and on bipartite matching - often the fastest practical algorithm when combined with link-cut trees.

The headline intuition: Ford-Fulkerson's correctness does not depend on path choice, but its running time does. Changing from DFS to BFS converts an exponential-in-value algorithm into a polynomial-in-structure one.

Why It Matters Here​

Moving from "Ford-Fulkerson method" to "a specific polynomial-time algorithm" is the practical transition from "flows exist in theory" to "I can use flows in a system."

  • Edmonds-Karp is what most introductory implementations actually are, even if they are called "Ford-Fulkerson." If you choose BFS for the augmenting path, you have Edmonds-Karp.
  • Capacity scaling is a cheap polynomial-time upgrade for graphs with huge but integer capacities; it pushes at least Delta units per augmentation, keeping iteration count bounded.
  • Push-relabel is the basis of the fastest practical max-flow libraries, including the ones used inside modern graph-cut segmentation tools (Boykov-Kolmogorov variant) and commercial network-flow solvers.

The three algorithms also illustrate distinct algorithmic paradigms: augmenting paths (Edmonds-Karp), parameterized search (capacity scaling), and preflow manipulation (push-relabel).

Concrete Example​

On the same network from the Ford-Fulkerson page:

Edmonds-Karp (BFS) trace:

iteraugmenting path (BFS)lengthbottlenecktotal flow
1s-a-t244
2s-b-c-t3913
3s-a-c-t3114
4no s-t path in residual--terminate

Max flow = 14. Notice BFS prevents the pathological long augmenting paths that adversarial graphs can exploit against arbitrary-path Ford-Fulkerson - each edge can be the bottleneck on at most |V|/2 augmentations because BFS path lengths are nondecreasing.

Capacity scaling on an adversarial graph:

s -(10^9)-> a, s -(10^9)-> b
a -(1)-> b
a -(10^9)-> t, b -(10^9)-> t

With Delta = 2^30, the algorithm ignores the (a,b) edge entirely and finishes in two augmentations. Plain Ford-Fulkerson with DFS that alternately chooses s-a-b-t and s-b-a-t would take 2 * 10^9 iterations.

Common Confusion / Misconceptions​

  • "Edmonds-Karp is Ford-Fulkerson with BFS." Yes, but the specific guarantee is that the augmenting-path length is nondecreasing across iterations, and each edge can be the bottleneck on at most O(|V|) augmentations. These two facts together yield O(|V| |E|^2); it is a nontrivial proof, not a restatement of Ford-Fulkerson.
  • "Push-relabel uses augmenting paths." It does not. It manipulates a preflow (which may temporarily violate conservation) and gradually pushes excess toward the sink using vertex heights; the structure is local rather than end-to-end.
  • "Capacity scaling is just Edmonds-Karp with integer math." No - it is a different control strategy: find only "big" augmenting paths, halve the threshold, repeat. The scaling trick is common in combinatorial optimization.
  • "Dinic is only for unit capacities." Dinic works on arbitrary capacities in O(|V|^2 |E|); the O(|E| sqrt(|V|)) bound is specific to unit-capacity and bipartite graphs.

How To Use It​

Default choice for this module: implement Ford-Fulkerson with BFS (Edmonds-Karp). It is clean, has a polynomial bound, and matches what interviews and systems questions expect.

If you need more performance, escalate in this order:

  1. Edmonds-Karp with fast adjacency-list traversal and reverse-pointer residuals.
  2. Capacity scaling on top of Edmonds-Karp when max capacity U is huge (for example, bandwidths in bytes).
  3. Dinic's algorithm, especially for bipartite matching (see Hopcroft-Karp) and unit-capacity networks.
  4. Push-relabel from an existing high-quality library (OR-Tools, Boost.Graph) when the graph is dense or push-relabel-friendly.

Skeleton for Edmonds-Karp:

while BFS from s in residual graph reaches t:
    reconstruct path via parent[]
    delta := min residual capacity along path
    push delta along path (decrement forward, increment reverse)
    total := total + delta
return total

Transfer / Where This Shows Up Later​

  • S3 (systems). Bandwidth shaping (tc), QoS, data-center fabric allocation - all use flow-based algorithms under the hood.
  • S4 (compilers). Register allocation via max-flow/min-cut formulations; instruction scheduling with resource constraints.
  • S5 (OS). I/O scheduling, process migration bandwidth planning; the Boykov-Kolmogorov max-flow appears in computer-vision kernels.
  • S6 (databases). Query optimization: push-relabel-like ideas for join ordering under memory bounds; transaction flow in lock managers.
  • S7 (DDD). Bounded-context capacity analysis, integration-bottleneck identification via min-cuts.
  • S8 (distributed). Traffic engineering in large networks, MPLS path computation, multi-commodity flow approximations.

Back-link to concept 17 (Ford-Fulkerson method), forward to concept 19 (max-flow/min-cut duality) and concept 20 (bipartite matching via flow).

Check Yourself​

  1. Why does picking a shortest augmenting path give polynomial time where arbitrary paths do not?
  2. What does capacity scaling buy over plain Edmonds-Karp?
  3. What is a "preflow" and how does it differ from a flow?
  4. Why is push-relabel's running time expressed in |V|^2 |E| rather than something in |E| alone?
  5. On a unit-capacity network, why does Dinic's run in O(|E| sqrt(|V|))?
  6. Show an adversarial graph where Edmonds-Karp beats DFS-Ford-Fulkerson by more than a factor of 100.

Mini Drill or Application​

Compare Ford-Fulkerson (DFS-chosen augmenting paths) and Edmonds-Karp (BFS) on the adversarial graph:

s -(1000)-> a, s -(1000)-> b
a -(1)-> b
a -(1000)-> t, b -(1000)-> t

Construct a sequence of augmenting paths for Ford-Fulkerson that forces 2000 iterations, and show that Edmonds-Karp terminates in at most 3 iterations.

Implementation drills.

  1. Implement Edmonds-Karp end-to-end with residual edges. Test on a 10-vertex network.
  2. Add capacity scaling on top; verify on the adversarial graph above - iteration count should drop by orders of magnitude.
  3. Write a simple push-relabel (FIFO order); verify same max-flow values as Edmonds-Karp on the same test set.
  4. Benchmark the three on random networks of 100/500/1000 vertices; produce a short comparison table.
  5. Plug your Edmonds-Karp into a project-selection instance: given 10 projects with revenues and prerequisite costs, compute the maximum-profit subset via max-flow/min-cut.

Read This Only If Stuck​