Improving Ford-Fulkerson

A Bad Example

Consider the following network:

s ──100── x
│         │
1         1
│         │
s ──100── y ──100── t

If the algorithm alternates between $s$-$x$-$y$-$t$ (bottleneck 1) and $s$-$y$-$x$-$t$ (bottleneck 1), up to 200 iterations may be needed, confirming the $O(mC)$ pseudo-polynomial bound is tight.

Capacity Scaling

Idea: Prioritize paths with larger residual capacities.

Definition 1. $G_f(\Delta)$ = the subgraph of $G_f$ containing only edges with residual capacity $\geq \Delta$.

f(e) ← 0  for all e
Δ ← largest power of 2 ≤ max capacity of edges leaving s
while Δ ≥ 1 do
    while Gf(Δ) has an s-t path do
        P ← simple s-t path in Gf(Δ)
        f ← Augment(f, P)
    Δ ← Δ/2
return f

This is a variant of Ford-Fulkerson with a specific path-selection rule, so correctness is immediate.

Lemma 1. The algorithm performs at most $2m\lceil 1 + \log_2 C \rceil$ augmentations.

Theorem 1. Time complexity: $O(m^2 \log_2 C)$ — weakly polynomial.

Edmonds-Karp Algorithm

Select augmenting paths with the fewest edges (BFS shortest path).

f(e) ← 0  for all e
while Gf has an s-t path do
    P ← s-t path with minimum number of edges in Gf (BFS)
    f ← Augment(f, P)
return f

Lemma 2. The Edmonds-Karp algorithm performs $O(mn)$ augmentations.

Theorem 2. Time complexity: $O(m^2 n)$ — strongly polynomial (bounded only by the number of input entries, not their values).

Note: Orlin (2012) gave an $O(mn)$-time algorithm, which is optimal but beyond our scope.

Bipartite Matching

Problem Definition

Definition 2. A graph $G = (V, E)$ is bipartite if $V = X \cup Y$ ($X \cap Y = \emptyset$) and every edge has one endpoint in $X$ and the other in $Y$.

Definition 3. A matching $M \subseteq E$: every vertex appears in $M$ at most once.

Problem (Maximum Bipartite Matching). Find a matching of maximum cardinality in bipartite graph $G = (X \cup Y, E)$.

Reduction to Maximum Flow

Orient all edges in $E$ from $X$ to $Y$ with capacity $\infty$.
Add source $s$ with edges $\langle s, x \rangle$ of capacity 1 for all $x \in X$.
Add sink $t$ with edges $\langle y, t \rangle$ of capacity 1 for all $y \in Y$.
Compute maximum integer flow $f^*$.
Output $M = \lbrace (x,y) : f^*(x,y) \neq 0\rbrace$.

Correctness Proof

Lemma 3. If $(x,y) \in E$ and $f^(x,y) \neq 0$, then $f^(x,y) = 1$.

Proof. The only incoming edge of $x$ is $\langle s,x \rangle$ with capacity 1, so $f^(x,y) \leq 1$ by flow conservation. Since $f^$ is integer, $f^*(x,y) = 1$. ∎

Lemma 4. $\lvert M\rvert \geq \text{OPT}$.

Proof. Fix maximum matching $O$. For each $(x,y) \in O$, send unit flow along $s$-$x$-$y$-$t$. Since $O$ is a matching, each edge is used at most once → valid flow of value $\lvert O\rvert$. Therefore $v(f^) \geq \lvert O\rvert = \text{OPT}$. With cut $S := \lbrace s\rbrace \cup X$, $v(f^) = \lvert M\rvert$ (by Lemma 3, no edges enter $S$). ∎

Lemma 5. Each $X$ node is incident to at most one edge of $M$.

Proof. If $x \in X$ had $\geq 2$ edges in $M$, then $f^{out}(x) \geq 2$ (by Lemma 3). But $c(s,x) = 1$ means $f^{in}(x) \leq 1$, contradicting flow conservation. ∎

Lemma 6. Each $Y$ node is incident to at most one edge of $M$. (Same argument as Lemma 5.)

Theorem 3. The algorithm returns a maximum bipartite matching. (Follows from Lemmas 4, 5, and 6.)

Time Complexity

Theorem 4. The algorithm runs in $O((m+n)n)$ time.

Proof. The constructed network has $n+2$ vertices and $m+n$ edges. Ford-Fulkerson computes integer flow in $O(m’ \cdot \lvert X\rvert) = O((m+n)n)$ time. ∎

Alternating Paths

Viewed from the bipartite matching perspective, each Ford-Fulkerson iteration finds an alternating path:

Alternates between $X$ and $Y$, using matched ($f \neq 0$) and unmatched edges alternately.
First and last edges are both unmatched.
Flipping matched/unmatched status along the path increases the matching size by 1.

An algorithm can directly search for alternating paths without explicitly constructing the flow network.