Ford-Fulkerson Method

Context: FIT2004_MOC · the W11 max-flow engine — repeatedly find an $s⇝t$ path in the residual network by DFS and push its bottleneck · proved optimal by the Min-Cut Max-Flow Theorem · reused unmodified by every reduction · PT-03: run max-flow/min-cut by hand, from a blank or a mid-stage network Parent Framework: Graph

Quick Revision

• 🎯 Objective: $|f|=0$ ➔ while the residual network has an $s⇝t$ path, push its bottleneck and update both edge directions ➔ no path left ⟹ the flow is maximum.
• 📦 Core Components: flow network (capacities $+$ two constraints) | residual network (forward $=$ spare, backward $=$ cancellable) | augmenting path ($O(V+E)$ BFS/DFS) | $\le F$ iterations ⟹ $O(FE)$.
• ⚡ Key Constraint: the backward edge is the whole method — pushing only along unused capacity sticks at $19$ on the lecture graph; cancelling $4$ units on $c\to b$ reaches $23$. And $O(FE)$ is pseudo-polynomial: $F$ is a value, not an input size.

📝 How It Works

1. The Flow Network and Its Two Constraints

• Flow network ➔ directed graph, every edge weighted by a non-negative capacity $c(u,v)$ · source $s$ has no incoming edges · target $t$ has no outgoing edges.
• Flow ➔ $f(u,v)$, drawn f/c on the edge; an edge carrying nothing may be drawn as bare $c$.
• Capacity constraint ➔ $0\le f(u,v)\le c(u,v)$ — “you can’t overload”.
• Flow conservation ➔ every $v\notin \{s,t\}$: ${\sum }_{E_{in}(v)}f={\sum }_{E_{out}(v)}f$ · lecture check at $b$: in $8+4+0=12$, out $1+11=12$.
• Value ➔ $|f|=$ net flow out of $s$ $=$ net flow into $t$ (equal by Min-Cut Max-Flow Theorem §2, applied P1).
• Max-flow problem ➔ find a valid $f$ maximising $|f|$ · the value is unique, the assignment is not (the lecture’s run and MUA’s slides both reach $23$ with different edge flows).

2. The Residual Network $G_f$ (a.k.a. potential network)

• Same vertices, edges re-derived from the current flow ➔ for each $u\to v$ in $G$:
  • forward / residual edge $u\to v$ of capacity $c(u,v)-f(u,v)$ ➔ room still unused.
  • backward / reversible edge $v\to u$ of capacity $f(u,v)$ ➔ flow already sent that may be cancelled.
• Drop zeros ➔ a saturated edge has no forward edge; an empty edge has no backward edge.
• Merge parallels ➔ $G_f$ is simple: $a\to b$ ($c=10$, $f=0$) and $b\to a$ ($c=4$, $f=1$) give $r(a,b)=10+1=11$, $r(b,a)=3+0=3$.
• Self-check ➔ $r(u,v)+r(v,u)=c(u,v)+c(v,u)$ — the slide’s “sum of the edges between 2 vertices same as the edge capacity”.
• Reading $G$ back off $G_f$ ➔ flow $=$ backward weight · capacity $=$ forward $+$ backward (the W11 sanity-check sheet writes “flow $=$ forward” — a slip; forward is $c-f$).
• Size ➔ at most $2E$ edges ⟹ built in $O(V+E)$.

3. Path Augmentation

• Augmenting path ➔ any $s⇝t$ path in $G_f$, found by BFS or DFS (BFS “is the best”) · forward and backward edges are traversed alike — “no discrimination”; they differ only at update time.
• Bottleneck ➔ $b=\min$ residual capacity along the path — the most that fits through every edge.
• Augment ➔ each path edge: forward ⟹ $f(u,v)+=b$ · backward ⟹ $f(v,u)-=b$ ➔ $|f|+=b$ ➔ refresh both residual directions · $O(1)$ per edge — each residual edge holds a pointer to its twin, so no search (§Core Implementation).
• What a backward edge means in $G$ ➔ re-routing, not reverse flow. Lecture, from $|f|=19$: path $s\to b\to c\to t$ ($b=\min (5,4,5)=4$) uses backward $b\to c$ ⟹ $c\to b$ drops $4\to 0$, $c$ sends those $4$ to $t$ instead, and $s\to b$ ($8\to 12$) refills $b$‘s lost inflow ⟹ $|f|=23$.
• Why a greedy push fails ➔ the direct route $s\to b\to d\to c\to t$ needs $d\to c$ (already $7/7$) — “we can’t, over capacity”; only the cancellation finds the extra $4$.

4. The Method

• Loop ➔ build $G_f$ ➔ while an augmenting path exists: take it, add its bottleneck to the flow, augment $G_f$ ➔ return the flow (lecture ford_fulkerson, slide 120).
• Invariant ➔ both constraints hold after every augment — the bottleneck never exceeds any residual capacity, and each interior path vertex gains and loses exactly $b$.
• “Method”, not “algorithm” ➔ path choice is left open; BFS vs DFS changes the iteration count, never the final value (§6).

5. Termination and Correctness

• Precondition ➔ every capacity is an integer.
• Termination ➔ integer residuals ⟹ $b\ge 1$ ⟹ $|f|$ rises by $\ge 1$ per iteration · $|f|$ is bounded (by the capacity out of $s$, or any cut) ⟹ at most $F$ iterations.
• Optimality ➔ termination alone does not prove maximum; that needs the Min-Cut Max-Flow Theorem — the vertices still reachable from $s$ form a cut whose capacity equals $|f|$ ➔ its §Proof Blueprint.
• W3 shape ➔ correctness $=$ termination $+$ a property at exit, exactly as in Invariant.
• Integrality bonus ➔ integer capacities ⟹ FF returns an integer flow on every edge — what lets reductions read matchings and $0/1$ entries straight off the flow.

6. Choosing the Path (slides flag as FIT3155 optimisation)

• Why path choice matters ➔ each iteration adds between $1$ and $F$; increments $8,13,41,\dots$ finish far sooner than $1,2,3,\dots$
• Fewest edges ➔ BFS ⟹ Edmonds–Karp ⟹ $O(V{E}^2)$, independent of $F$ (proof in FIT3155) · fewer edges, lower chance of a small capacity on the path.
• Largest bottleneck ➔ the lecture’s route is a maximum spanning tree — the bottleneck idea from Minimum Spanning Tree §4.

🔭 Beyond the lecture (the sanity check poses "explain $O(V{E}^2)$" as D/HD; the argument is not in the provided material)

• Distances never shrink ➔ augmenting along BFS shortest paths keeps every ${\delta }_f(s,v)$ in $G_f$ non-decreasing.
• Each edge is the bottleneck $\le V/2$ times ➔ a bottleneck edge $u\to v$ leaves $G_f$; it returns only after a later path uses $v\to u$, which pushes $\delta (s,u)$ up by $\ge 2$, and distances are capped at $V$.
• Count ➔ $\le 2E$ residual edges $\times V/2$ ⟹ $O(VE)$ augmentations $\times O(E)$ per BFS ⟹ $O(V{E}^2)$, independent of $F$.

⚙️ Core Implementation

🔹 Ford-Fulkerson with BFS (applied P8) — paired residual edges

Code

from collections import deque
 
class Edge:
    def __init__(self, v, cap, rev):
        self.v, self.cap, self.rev = v, cap, rev   # cap = RESIDUAL capacity; rev = twin's index in adj[v]
 
def add_edge(adj, u, v, c):
    adj[u].append(Edge(v, c, len(adj[v])))         # forward:  spare = c
    adj[v].append(Edge(u, 0, len(adj[u]) - 1))     # backward: cancellable = 0
 
def ford_fulkerson(adj, s, t):
    flow = 0
    while True:
        parent = [None] * len(adj)                  # rebuilt EVERY iteration
        parent[s] = (s, None)
        q = deque([s])                              # q.pop() instead => DFS variant
        while q and parent[t] is None:              # 1. augmenting path   O(V+E)
            u = q.popleft()
            for e in adj[u]:
                if e.cap > 0 and parent[e.v] is None:
                    parent[e.v] = (u, e)
                    q.append(e.v)
        if parent[t] is None:                       # no path => maximum
            return flow
        b, v = float('inf'), t                      # 2. bottleneck        O(V)
        while v != s:
            u, e = parent[v]
            b = min(b, e.cap)
            v = u
        v = t                                       # 3. augment           O(V)
        while v != s:
            u, e = parent[v]
            e.cap -= b                              # forward loses b
            adj[v][e.rev].cap += b                  # twin gains b (cancellable)
            v = u
        flow += b

• Edge flow afterwards ➔ $f(u,v)=c(u,v)-$ e.cap on each forward edge.
• Twins replace merging ➔ antiparallel input edges keep separate twins instead of one merged residual edge — same reachability, same answer. 💡 Common Mistake: Updating only e.cap ➔ without adj[v][e.rev].cap += b no backward edge ever appears and the method degenerates into the greedy push that sticks at $19$.

⚖️ Complexity

Step / variant	Time	Aux space	Why
Build $G_f$	$O(V+E)$	$\Theta (V+E)$	$\le 2E$ residual edges
One iteration	$O(V+E)$	$\Theta (V)$	one BFS/DFS $+$ two $O(V)$ path walks
Iterations	$\le F$	—	integer capacities ⟹ $b\ge 1$
FF, any path (DFS)	$O(F(V+E))=O(FE)$	$\Theta (V+E)$	$E\ge V-1$ once every vertex lies on an $s$–$t$ path
FF with BFS (Edmonds–Karp)	$O(\min (FE,V{E}^2))$	$\Theta (V+E)$	$V{E}^2$ is D/HD-level (sketch: §6 🔭)
Unit capacities	$O(VE)$	$\Theta (V+E)$	$F\le {\mathrm{deg}}^{+}(s)\le V-1$ (Network Flow Reductions §4)

• Pseudo-polynomial ➔ $F$ is a number in the input; capacities near $2^{32}$ make $F$ exponential in the input’s bit-length (Algorithmic Complexity) even though $V$ and $E$ are tiny.

📊 Exam Execution Trace & Applied Exercises

Lecture graph: $s\to a16$, $s\to b13$, $a\to b10$, $b\to a4$, $a\to c12$, $c\to b9$, $b\to d14$, $d\to c7$, $c\to t20$, $d\to t4$.

Manual Execution Trace — lecture trial run from $|f|=0$

Iter	Augmenting path in $G_f$	Residual caps on path	$b$	$|f|$	Newly saturated
$1$	$s\to a\to c\to t$	$16,12,20$	$12$	$12$	$a\to c$
$2$	$s\to b\to d\to t$	$13,14,4$	$4$	$16$	$d\to t$
$3$	$s\to b\to d\to c\to t$	$9,10,7,8$	$7$	$23$	$d\to c$
$4$	none — from $\{s,a,b,d\}$ every exit is saturated	—	—	$23$	stop

Final Extracted Output: $|f|=23$ · $s\to a12/16$ · $s\to b11/13$ · $a\to c12/12$ · $b\to d11/14$ · $d\to c7/7$ · $d\to t4/4$ · $c\to t19/20$ · all others $0$. The reached set $\{s,a,b,d\}$ in iteration $4$ is the min cut ➔ Min-Cut Max-Flow Theorem §4.

Applied Exercise — prep P1: warm start, one cancellation per round

Problem: $s\to a1/3$, $s\to b4/4$, $b\to a1/1$, $a\to c5/5$, $d\to a3/4$, $c\to d0/1$, $c\to t5/5$, $b\to d3/4$, $d\to t0/3$ ⟹ $|f|=5$. Residual (a): $s\to a2$ · $a\to s1$ · $b\to s4$ · $a\to b1$ (cancel $b\to a$) · $c\to a5$ · $a\to d3$ (cancel $d\to a$) · $d\to a1$ · $c\to d1$ · $t\to c5$ · $b\to d1$ · $d\to b3$ · $d\to t3$.

$$\begin{array}{rl}\text{Aug 1: }& s\to a\to b\to d\to t,b=\min (2,1,1,3)=1\Rightarrow b\to a1\to 0,b\to d3\to 4,d\to t0\to 1,|f|=6\\ \text{Aug 2: }& s\to a\to d\to t,b=\min (1,3,2)=1\Rightarrow d\to a3\to 2,s\to a2\to 3,d\to t1\to 2,|f|=7\\ \text{Stop: }& s\to a3/3\text{ and }s\to b4/4\Rightarrow s\text{ has no residual out-edge}\end{array}$$

Final Extracted Output: $|f|=7$ · both augments run through a backward edge ($a\to b$, then $a\to d$) · other paths give other valid final networks ➔ min cut $(\{s\},\text{rest})$ in Min-Cut Max-Flow Theorem §Applied.

⚠️ Common Mistakes

• 💡 Bottleneck from original capacities ➔ use residual ones: prep $s\to a$ has $c=3$ but residual $2$.
• 💡 Drawing a backward edge into $G$ ➔ a backward edge lives only in $G_f$; augmenting along it decreases the flow on the real edge, it never creates a reverse edge.
• 💡 Calling $O(FE)$ polynomial ➔ it is pseudo-polynomial; the polynomial bound needs BFS ($O(V{E}^2)$).
• 💡 Mid-stage start with forward edges only ➔ a PT-03 network that already carries flow usually needs a backward augment; verify by re-running from blank — the max-flow value must match.
• 💡 “The max flow” ➔ the value is unique, the edge assignment is not — mark schemes accept any valid final network.

🧠 Active Recall

Why does the residual network need backward edges? Give the lecture case that breaks without them.

Answer

• Short answer: an early path can route flow badly; backward edges let a later path cancel it, which no forward-only search can do.
• Why: At $|f|=19$ ➔ every forward route to $t$ is blocked ($d\to c$ is $7/7$), so a forward-only search stops at $19$. Backward $b\to c$ ($=f(c,b)=4$) ➔ path $s\to b\to c\to t$ moves $c$‘s $4$ units off $c\to b$ onto $c\to t$ and refills $b$ from $s$ ⟹ $23$. Optimality depends on it ➔ the Min-Cut Max-Flow Theorem proof needs “no residual path” to mean every T$\to$S edge is empty, which only holds when cancellation was possible.

Why is Ford-Fulkerson $O(FE)$, and why is that pseudo-polynomial?

• Hint: count iterations by the flow, not by the graph.

Answer

• Short answer: $\le F$ iterations of $O(V+E)$ each; $F$ is a capacity value, so it can be exponential in the input’s bit-length.
• Why: Per iteration ➔ one BFS/DFS over $G_f$ ($\le 2E$ edges) $+$ $O(V)$ to read and augment the path. Iterations ➔ integer capacities make each bottleneck $\ge 1$, so at most $F$ rounds. Illustration (not in the slides) ➔ diamond $s\to a$, $s\to b$, $a\to t$, $b\to t$ at $10^6$ plus $a\to b$ at $1$: a DFS alternating $s\to a\to b\to t$ and $s\to b\to a\to t$ augments by $1$ each time ⟹ $2\times 10^6$ rounds, while BFS takes the two 2-edge paths ⟹ $2$ rounds.

BFS or DFS for the augmenting path — does it change correctness, the answer, or the bound?

Answer

• Short answer: neither correctness nor the value; only the bound — any path gives $O(FE)$, BFS adds $O(V{E}^2)$.
• Why: Correctness ➔ the proof uses only “no augmenting path at exit”, which holds for any search. Value ➔ the max flow equals the min cut capacity, a property of the network alone. Bound ➔ BFS picks a fewest-edge path (Edmonds–Karp), capping iterations at $O(VE)$ independent of $F$ — the FIT3155 result the slides quote.