Prerequisite: Minimum Spanning Trees & Union-Find

Overview

A flow network is a directed graph $G = (V, E)$ with a capacity function $c : E \to \mathbb{R}_{\geq 0}$, a designated source $s$, and a sink $t$. A flow $f : E \to \mathbb{R}$ must satisfy:

  • Capacity constraint: $0 \leq f(u,v) \leq c(u,v)$ for all $(u,v) \in E$.
  • Conservation: $\sum_v f(u,v) = \sum_v f(v,u)$ for all $u \neq s, t$ (flow in equals flow out).

The value of the flow is $|f| = \sum_v f(s,v) - \sum_v f(v,s)$. The goal is to find a flow of maximum value.

Max-Flow Min-Cut Theorem

An $s$-$t$ cut $(S, T)$ partitions $V$ into $S \ni s$ and $T \ni t$. Its capacity is

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

The max-flow min-cut theorem states: the value of a maximum flow equals the capacity of a minimum $s$-$t$ cut.

Proof sketch. Let $f^\ast$ be a maximum flow. Define the residual graph $G_f$: for each edge $(u,v)$ with capacity $c$ and flow $f$, add a forward residual edge of capacity $c - f$ and a backward edge of capacity $f$. An augmenting path is an $s$-$t$ path in $G_f$. If no augmenting path exists, let $S$ be the set of vertices reachable from $s$ in $G_f$. Then every edge $(u,v)$ with $u \in S$, $v \notin S$ must be saturated ($f(u,v) = c(u,v)$) and every edge $(v,u)$ carries zero flow. Therefore

$$|f^\ast| = \sum_{u \in S, v \in T} f(u,v) - \sum_{u \in S, v \in T} f(v,u) = c(S,T).$$

Since $|f| \leq c(S,T)$ for any flow and any cut (flows cannot exceed cut capacities), this cut is minimum and $f^\ast$ is maximum. $\square$

Ford-Fulkerson Framework

The Ford-Fulkerson method repeatedly finds an augmenting path in $G_f$ and pushes flow along it.

FordFulkerson(G, s, t):
    f = 0 (zero flow on all edges)
    while exists augmenting path p in G_f:
        bottleneck = min capacity along p in G_f
        augment flow along p by bottleneck
        update G_f
    return f

Complexity. If augmenting paths are found by DFS (or any search), each iteration increases the integer flow by at least 1. For integer capacities with max flow value $F$: $O(F)$ augmentations, each costing $O(E)$, gives $O(EF)$. This is pseudo-polynomial - poor when $F$ is large.

Edmonds-Karp Algorithm

Edmonds-Karp fixes the path-finding strategy: always use BFS (shortest augmenting path in terms of number of edges).

Complexity. Each BFS augmentation takes $O(E)$. The key insight is that the distance from $s$ to any vertex in $G_f$ never decreases across augmentations, and each edge can become a bottleneck at most $O(V)$ times before the distance bound increases. Total augmentations: $O(VE)$. Total time: $O(VE^2)$.

This is a polynomial bound independent of the flow values - a significant improvement over basic Ford-Fulkerson.

Dinic’s Algorithm

Dinic’s algorithm builds a level graph $L_f$ containing only edges on shortest augmenting paths, then pushes a blocking flow - a flow in $L_f$ that saturates every $s$-$t$ path in $L_f$.

Dinic(G, s, t):
    f = 0
    while BFS on G_f finds s-t path:
        build level graph L_f
        while blocking_flow = BlockingFlow(L_f) has f > 0:
            augment f by blocking_flow
            update G_f
    return f

Complexity. Each phase (one level-graph build + blocking flow) increases the shortest augmenting-path length by at least 1. Since path length is bounded by $V-1$, there are at most $O(V)$ phases. Each blocking flow takes $O(VE)$ using DFS with advance/retreat. Total: $O(V^2 E)$.

For unit-capacity networks (each $c(e) \in {0,1}$), path length is bounded by $O(\sqrt{E})$ phases, giving $O(E \sqrt{V})$ - this is the foundation of Hopcroft-Karp for bipartite matching.

Bipartite Matching and König’s Theorem

A bipartite matching problem has a bipartite graph $G = (U \cup W, E)$ and seeks the largest subset of edges with no two sharing an endpoint.

Reduction to max flow. Add source $s$ with edges $c(s, u) = 1$ to all $u \in U$, and sink $t$ with edges $c(w, t) = 1$ from all $w \in W$; set $c(u,w) = 1$ for all $(u,w) \in E$. A maximum integer flow in this network equals the size of a maximum matching.

König’s theorem. In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover (a set of vertices that touches every edge). This is a direct corollary of max-flow min-cut: a minimum cut in the flow network corresponds to a minimum vertex cover in the original graph.

Hopcroft-Karp. By applying Dinic’s on unit-capacity bipartite graphs: $O(E\sqrt{V})$. It finds shortest augmenting paths in batches using BFS + DFS.

Hungarian Algorithm (Assignment Problem)

Given an $n \times n$ cost matrix $C$ (or bipartite graph with weights), the assignment problem seeks a perfect matching minimising total cost. The Hungarian algorithm:

  1. Subtract row and column minima to create a zero-cost structure.
  2. Cover all zeros with a minimum set of lines (König’s theorem gives the count).
  3. If $n$ lines are needed, a perfect matching among zeros is optimal.
  4. Otherwise, adjust the matrix to create new zeros and repeat.

Time complexity: $O(n^3)$ with careful implementation (or $O(VE)$ using augmenting paths in the bipartite graph).

Applications: Project Selection and Image Segmentation

Project selection. Given projects with profits and machines with costs, where projects require certain machines: model as a flow network. Projects are connected to $s$ with capacity = profit; machines connect to $t$ with capacity = cost; project-machine dependencies have $\infty$ capacity. A minimum $s$-$t$ cut selects which projects to pursue and which machines to buy, maximising profit minus cost.

Graph-cut image segmentation (GrabCut). Each pixel is a node; neighbouring pixels share edges whose capacity encodes colour similarity. Source $s$ represents “foreground” and sink $t$ represents “background”. A minimum $s$-$t$ cut partitions pixels into foreground and background, balancing the unary term (how likely each pixel is foreground/background) against the pairwise term (how different adjacent pixels are). Dinic’s algorithm handles the dense grid graphs efficiently.

Examples

Task assignment. A company has $n$ workers and $m$ jobs; each worker can do a subset of jobs. Maximum bipartite matching finds the largest number of jobs that can be simultaneously assigned (one worker per job). If a perfect matching exists, König’s theorem also identifies the smallest set of workers that “covers” all jobs.

Network bandwidth. A data-centre operator models its switching fabric as a flow network with link capacities. Ford-Fulkerson (or Dinic’s) computes the maximum aggregate throughput from ingress to egress nodes; the min-cut identifies the bottleneck links that limit overall bandwidth.

Baseball elimination. Team $i$ is eliminated if even optimistically (assuming they win all remaining games) they cannot tie for first. This reduces to a max-flow problem: if the max flow is less than the total remaining games among a subset of teams, some team mathematically cannot reach first place.

Read Next: