Network flow — max-flow min-cut theorem, Ford-Fulkerson, Edmonds-Karp

WHAT we are modelling

WHY max-flow = min-cut (derivation from scratch)

Step 1 — Flow across any cut equals $|f|$ .

Take any cut $(S,T)$ . Sum the conservation equation over all nodes in $S$ . Internal edges (both endpoints in $S$ ) appear once as $+f$ and once as $-f$ and cancel. What survives is only flow crossing the cut: $|f| = \sum_{u\in S,\,v\in T} f(u,v) \;-\; \sum_{u\in S,\,v\in T} f(v,u)$ Why this step? Conservation forces everything inside $S$ to balance, so the net out of $S$ must equal the net out of $s$ , which is $|f|$ .

Step 2 — Weak duality: every flow ≤ every cut. $|f| = \underbrace{\sum f(\text{forward})}_{\le\, c} - \underbrace{\sum f(\text{backward})}_{\ge\, 0} \;\le\; \sum c(\text{forward}) = c(S,T)$ Why? Forward flows are capped by capacity; backward flows are subtracted and are $\ge 0$ . So any flow value is bounded by any cut capacity. Hence $\max|f| \le \min c(S,T)$ .

Step 3 — Equality is achievable (the max-flow min-cut theorem).

When a flow is maximum, there is NO augmenting path in the residual graph (defined next). Let $S=$ all nodes reachable from $s$ in the residual graph, $T$ = the rest. Then $t\notin S$ . For this cut:

every forward edge $u\to v$ ( $u\in S,v\in T$ ) is saturated ( $f=c$ ), else $v$ would be reachable;
every backward edge carries $f=0$ , else it would give a residual edge into $T$ .

Plug into Step 1: $|f| = \sum c(\text{forward}) - 0 = c(S,T)$ . So this flow equals a cut capacity, and by Step 2 both are optimal. $\blacksquare$

The residual graph (the engine of all algorithms)

An augmenting path is any $s\to t$ path in the residual graph. Its bottleneck is the minimum $c_f$ along it; pushing that much strictly increases $|f|$ .

Ford–Fulkerson (the method)

Formula Ford–Fulkerson

f = 0
while there exists an augmenting path P in residual G_f:
    b = min residual capacity along P
    push b along P:  forward edges f += b, backward edges f -= b
return f

HOW it terminates / is correct: when no augmenting path exists, by the theorem $f$ is maximum.

Complexity: with integer capacities, each iteration adds $\ge 1$ , so $O(E\cdot|f^*|)$ . With a bad path choice this can be slow (value-dependent). With irrational capacities it may not even terminate!

Edmonds–Karp (a smart path rule)

Figure — Network flow — max-flow min-cut theorem, Ford-Fulkerson, Edmonds-Karp

Worked Example 1 — push & augment by hand

Network: $s\to a$ (cap 3), $s\to b$ (2), $a\to b$ (1), $a\to t$ (2), $b\to t$ (3).

Path 1: $s\to a\to t$ , bottleneck $=\min(3,2)=2$ . Push 2. Why? $a\to t$ is the limiter. Path 2: $s\to b\to t$ , bottleneck $=\min(2,3)=2$ . Push 2. Path 3: $s\to a\to b\to t$ , residual: $s\to a$ has $3-2=1$ , $a\to b=1$ , $b\to t=3-2=1$ . Bottleneck $=1$ . Push 1. Now $|f| = 2+2+1 = 5$ . Why no more? $s$ 's out-capacity is $3+2=5$ , all saturated — this is the min cut $S=\{s\}$ , $c=5$ . Max flow = 5. ✔

Worked Example 2 — backward edge saves the day

$s\to a$ (1), $s\to b$ (1), $a\to b$ (1), $a\to t$ (1), $b\to t$ (1).

Greedy picks $s\to a\to b\to t$ , bottleneck 1. Why might we panic? Now $a\to t$ and $s\to b$ look unusable. But residual has backward $b\to a$ (cap 1). New path: $s\to b\to a\to t$ ? — $s\to b$ (1), backward $b\to a$ (1), $a\to t$ (1). Push 1. Total $=2$ = min cut. Why this step? The backward edge undid the bad commitment $a\to b$ , freeing $a\to t$ . ✔

Recall Feynman: explain to a 12-year-old

Imagine water pipes from a tap to a bucket. Each pipe can only carry so much. You want maximum water reaching the bucket. The limit is the weakest place in the network — find the cheapest set of pipes to cut so no water gets through, and that's exactly the max water you can send. The algorithm keeps finding "still-open routes," pushes water, and is even allowed to take water back from a route it tried earlier and send it a better way. When no open route is left, you're done — you've hit the bottleneck.

Flashcards

What does a flow network require on each edge and which two special nodes?

A capacity

c(u,v)\ge0

; a source

s

and a sink

t

State the two constraints a valid flow must satisfy.

Capacity (

0\le f\le c

) and conservation (in-flow = out-flow at every non-

s,t

node).

Define the capacity of an s–t cut

(S,T)

c(S,T)=\sum_{u\in S,v\in T} c(u,v)

— only forward

S\to T

edges.

State the max-flow min-cut theorem.

\max |f| = \min c(S,T)

; max flow value equals the minimum cut capacity.

What are the three equivalent conditions for a flow being maximum?

(a)

f

max, (b) no augmenting path in residual graph, (c)

|f|=c(S,T)

for some cut.

What is the residual capacity of edge

(u,v)

, and what backward edge appears?

c_f(u,v)=c(u,v)-f(u,v)

; plus backward edge

v\to u

with capacity

f(u,v)

Why do we need backward residual edges?

To undo/re-route previously committed flow so greedy mistakes can be corrected.

What is an augmenting path and how much flow does it carry?

s\to t

path in the residual graph; carries its bottleneck = min residual capacity along it.

Ford-Fulkerson complexity with integer capacities?

O(E\cdot|f^*|)

— depends on the max-flow value (can be slow).

What rule defines Edmonds-Karp and what's its complexity?

Always augment along the BFS-shortest path;

O(VE^2)

, independent of capacities.

Why is Edmonds-Karp capacity-independent?

BFS distances never decrease; each edge is saturated

O(V)

times →

O(VE)

augmentations ×

O(E)

BFS.

How do you recover the min cut after running max flow?

S

= nodes reachable from

s

in the final residual graph;

T

= rest. Forward edges across are saturated.

Why does flow across any cut equal

|f|

Summing conservation over

S

cancels internal edges, leaving net flow out of

S

= net flow out of

s

|f|

Connections

Graphs — base data structure & traversal
BFS — the shortest-augmenting-path engine of Edmonds-Karp
Bipartite Matching — solved as unit-capacity max flow
Linear Programming Duality — max-flow/min-cut is its combinatorial special case
Dinic's Algorithm — faster $O(V^2E)$ via level graphs + blocking flows
Menger's Theorem — edge/vertex disjoint paths = a flow corollary

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho ek paani ke pipe ka network hai — ek source (tap) $s$ se ek sink (bucket) $t$ tak. Har pipe ki ek max capacity hai. Sawaal: kitna paani per second $s$ se $t$ tak bhej sakte ho? Iska jawab network ke sabse weak hisse pe depend karta hai — wo minimum set of pipes jinhe kaat do toh paani ruk jaaye. Yahi hai max-flow = min-cut ka magic: maximum flow ki value bilkul minimum cut ki capacity ke barabar hoti hai.

Algorithm kaise chalta hai? Ford-Fulkerson bolta hai: jab tak source se sink tak koi augmenting path (residual graph mein khula rasta) milta rahe, usme bottleneck (minimum bachi capacity) ke barabar paani push karte raho. Sabse zaroori cheez hai backward edges — yeh tumhe purana galat decision undo karne dete hain. Jaise pehle ek route pe paani bhej diya tha jo aage jaake fas gaya, toh backward edge se wapas le ke better route pe bhej sakte ho. Isliye greedy galti nahi karta.

Edmonds-Karp sirf ek smart twist hai: hamesha BFS se shortest path chuno augment karne ke liye. Isse complexity capacity values pe depend nahi karti, fixed $O(VE^2)$ ho jaati hai — bahut reliable. Plain Ford-Fulkerson galat path choose kare toh slow ho sakta hai ( $O(E\cdot|f|)$ ).

Yeh topic kyun important hai? Bipartite matching, image segmentation, scheduling, network reliability — sab ke andar yahi max-flow chhupa hota hai. Aur jab interview mein poochhe "max flow kaise prove karoge done?", jawab yaad rakho: residual graph mein koi augmenting path na bache, tabhi flow maximum hai, aur reachable nodes ka set $S$ ban jaata hai min cut.

Network flow — max-flow min-cut theorem, Ford-Fulkerson, Edmonds-Karp

WHAT we are modelling

WHY max-flow = min-cut (derivation from scratch)

The residual graph (the engine of all algorithms)

Ford–Fulkerson (the method)

Edmonds–Karp (a smart path rule)

Worked Example 1 — push & augment by hand

Worked Example 2 — backward edge saves the day

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Graphs

Connections