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

Check the two rules from the parent note. Capacity ($0\le f\le c$): $3\le 4$ ✔, $1\le 2$ ✔, $2\le 3$ ✔, $1\le 2$ ✔, $1\le 2$ ✔, $3\le 4$ ✔. Conservation at each interior node (in = out):

• $a$: in $=f(s,a)=3$; out $=f(a,c)+f(a,t)=2+1=3$ ✔
• $b$: in $=f(s,b)=1$; out $=f(b,c)=1$ ✔
• $c$: in $=f(a,c)+f(b,c)=2+1=3$; out $=f(c,t)=3$ ✔

Valid. Value $|f|=f(s,a)+f(s,b)=3+1=4$.

Only edges going forward from $S$ to $T$ count (Blunder 2 in the parent note). Edges leaving $\{s,a\}$ into $\{b,c,t\}$:

• $s\to b$ (cap 2)
• $a\to c$ (cap 3)
• $a\to t$ (cap 2)

($s\to a$ stays inside $S$, so it does not count.) $c(S,T)=2+3+2=7$.

Forward leftover: $c_f(a,c)=c(a,c)-f(a,c)=3-2=1$. Backward (undo) edge $c\to a$ has capacity $=f(a,c)=2$.

Start $f=0$.

• Path $s\to a\to t$: bottleneck $\min (4,2)=2$. Push 2. Running $|f|=2$.
• Path $s\to a\to c\to t$: residual $s\to a=4-2=2$, $a\to c=3$, $c\to t=4$. Bottleneck $\min (2,3,4)=2$. Push 2. $|f|=4$.
• Path $s\to b\to c\to t$: $s\to b=2$, $b\to c=2$, $c\to t=4-2=2$. Bottleneck $\min (2,2,2)=2$. Push 2. $|f|=6$.

Any more? Out of $s$: $s\to a$ has $4-4=0$ left, $s\to b$ has $2-2=0$ left. Source is fully saturated, so no residual edge leaves $s$. Max flow $=6$. Matching min cut: $S=\{s\}$, $c(S,T)=c(s,a)+c(s,b)=4+2=6$ ✔.

BFS measures path length in edges. From $s$, shortest $s-t$ paths have length 2: $s\to a\to t$ and $s\to b\to t$. BFS picks one such length-2 path first — say $s\to a\to t$, bottleneck 1, push 1. Residual: $s\to a$ gone, $a\to t$ gone; still open $s\to b$, $b\to t$. Next BFS shortest path: $s\to b\to t$, length 2, bottleneck 1, push 1. $|f|=2$. No residual path remains ($s$ fully saturated). Max flow $=2$. Note Edmonds–Karp's shortest-path rule avoided the length-3 detour $s\to a\to b\to t$ that plain Ford–Fulkerson might grab first.

If the path chooser is adversarial and always routes through the unit middle edge, each augmentation pushes only bottleneck 1 (the $a\to b$ edge), so it needs $2M=2000$ augmentations to reach the true max flow $2M=2000$. This is the value-dependent $O(E\cdot |f^{\ast }|)$ blow-up. Edmonds–Karp ignores the middle edge because $s\to a\to t$ and $s\to b\to t$ are shorter (length 2 vs 3). It pushes $M$ then $M$: just 2 augmentations. Max flow $=2M=2000$ in both cases — same answer, wildly different work.

Take $S=\{s\}$, $T=\{a,b,c,t\}$. Forward edges: $s\to a$ (4), $s\to b$ (2). $c(S,T)=4+2=6$. By weak duality (Step 2 of the parent proof), every flow $\le$ every cut, so $|f|\le 6$. We achieved $|f|=6$. Equality means both are optimal — the max-flow min-cut theorem. The saturated source edges are the bottleneck.

At max flow, $s\to a$ and $s\to b$ are both saturated (residual 0), so no forward residual edge leaves $s$. Are there backward residual edges into $s$? Backward edges point $a\to s$, $b\to s$ — those go toward $s$, not away, so they don't help reach new nodes. Hence $S=\{s\}$ and $T=\{a,b,c,t\}$. This is exactly the cut of L3.1, capacity $6$. The construction (“reachable set in residual graph”) is precisely Step 3 of the theorem's proof.

Push 1 along $s\to a\to b\to t$. Now $s\to a$, $a\to b$, $b\to t$ are all saturated. Remaining forward edges: $s\to b$ (open), $a\to t$ (open) — but there is no forward path connecting them ($s\to b\to ?$ dead-ends since $b\to t$ is full; $a\to t$ is unreachable since $s\to a$ is full). Greedy stops at $|f|=1$. With backward edges, the residual graph has $b\to a$ (cap 1, the undo of $a\to b$). New path: $s\to b\to a\to t$ using $s\to b$(1), backward $b\to a$(1), $a\to t$(1). Push 1. Now $|f|=2$, which equals the min cut $S=\{s\}$: $c(s,a)+c(s,b)=1+1=2$. The backward edge re-routed the mistaken commitment.

Standard Bipartite Matching reduction: add source $s\to w_i$ (cap 1 each), edge $w_i\to j_k$ (cap 1) for each allowed pair, and $j_k\to t$ (cap 1 each). Max flow = max matching (each unit of flow is one matched pair; capacity-1 source/sink edges force distinctness). Trace: $s\to w_1\to j_1\to t$ (1), $s\to w_2\to j_2\to t$ (1), $s\to w_3\to j_3\to t$ (1). All three source edges saturated. Max matching $=3$ — a perfect matching. Certificate: cut $S=\{s\}$ has capacity $=3$ (three unit source edges), matching the flow.

With all capacities 1, max flow counts edge-disjoint paths (each path uses each edge at most its capacity 1). Push:

• $s\to a\to t$ (1)
• $s\to b\to c\to t$ (1)

Now $s\to a$ used, $a\to t$ used; $s\to b$, $b\to c$, $c\to t$ used. Remaining: $a\to c$ (1) but $s\to a$ is full so $a$ is unreachable. Max flow $=2$, so 2 edge-disjoint paths. By Menger's Theorem (the edge form = max-flow min-cut with unit capacities), the minimum number of edges whose removal disconnects $s$ from $t$ is also $2$. Min cut: $S=\{s,a\}$ gives forward edges $s\to b$, $a\to c$, $a\to t$ = capacity 3... but the tight cut is $S=\{s\}$: edges $s\to a$, $s\to b$ = 2 ✔.

Primal (max flow): variables $f(u,v)\ge 0$, maximize $|f|$ subject to $f\le c$ and conservation. Its dual assigns a variable to each edge (interpretable as a 0/1 “is this edge cut?” indicator in the integral optimum) and minimizes total cut capacity. Strong Linear Programming Duality gives primal optimum = dual optimum, i.e. $\max |f|=\min c(S,T)$ — the max-flow min-cut theorem is exactly LP duality specialised to this totally-unimodular problem (so the LP optimum is integral). No numeric answer; the point is the structural identity.

Edmonds–Karp: $V{E}^2=50\cdot 400^2=50\cdot 160000=8000000$ — capacity-independent. Ford–Fulkerson (worst path choice): $E\cdot |f^{\ast }|=400\cdot 10^6=4\times 10^8$ — 50× larger and it depends on the capacity magnitude. The capacity-independent $V{E}^2$ bound is the safe one to quote. (If you needed even better, Dinic's Algorithm gives $O(V^{2}E)$, and $O(E\sqrt{V})$ on unit-capacity/matching graphs.)

(a) $s=t$: value $|f|=\sum f(s,v)-\sum f(v,s)$ is defined as net flow out of the source, but source is the sink — the problem is degenerate; conventionally max flow $=0$ (nothing to transport). Most implementations reject $s=t$. (b) No $s\to t$ path: no augmenting path ever exists, so max flow $=0$. The min cut is $c=0$: put every $s$-reachable node in $S$; since $t$ is unreachable, no forward edge crosses. ✔ theorem holds trivially. (c) Capacity-0 edge: $c(u,v)=0$ forces $f(u,v)=0$ by the capacity constraint; the edge is as good as absent and contributes 0 to any cut. Max flow unchanged. (d) Self-loop $a\to a$ (cap 5): conservation at $a$ counts it as both in-flow and out-flow, so it cancels; it can carry any $f\le 5$ but never changes $|f|$. Safe to delete before running. Max flow unchanged.

Each augmentation pushes along a shortest residual path, so it only adds residual edges that are the reverse of edges on that shortest path. A reverse edge $(v,u)$ appears only when $(u,v)$ lay on a shortest path, meaning $\delta (s,v)=\delta (s,u)+1$; using the new reverse edge later would require $\delta (s,u)=\delta (s,v)+1$, i.e. $\delta (s,u)$ grew by $\ge 2$. So between two saturations of the same edge, a distance increases by at least 2. Distances are bounded by $V$, so each of the $E$ edges is saturated $O(V)$ times, giving $O(VE)$ augmentations; each BFS costs $O(E)$, hence $O(V{E}^2)$ total. $■$

Max flow of Network A ::: 6 Max flow of Network B ::: 2 Edge-disjoint $s\to t$ paths in unit-capacity Network A ::: 2 Edmonds–Karp bound for $V=50,E=400$ ::: $8000000$