1. The Core Mathematical Constraints of Network Flow

Before we look at the algorithm, we must mathematically define a **Flow Network**.

A flow network is a directed graph $G = (V, E)$ where each edge $(u, v) \in E$ is assigned a non-negative **capacity** $c(u, v) \ge 0$. If an edge $(u, v)$ does not exist in the graph, its capacity is implicitly zero. We designate two special nodes: the **Source** ($s$), which produces flow, and the **Sink** ($t$), which consumes it.

A **Flow** is a real-valued function $f: V \times V \to \mathbb{R}$ that maps pairs of vertices to values. A valid flow function must strictly satisfy three constraints:

1.1 Capacity Constraint

The flow pushed along any edge cannot exceed the capacity of that edge.

1.2 Skew Symmetry

The flow from node $u$ to node $v$ must be the exact negative of the flow from $v$ to $u$. This represents cancellation: pushing 5 units of flow from $A$ to $B$ is mathematically equivalent to pushing -5 units from $B$ to $A$.

1.3 Flow Conservation

For any node that is neither the source $s$ nor the sink $t$, the sum of incoming flow must equal the sum of outgoing flow. In other words, intermediate nodes cannot store, create, or destroy flow.

2. Augmenting Paths and Residual Networks

To solve the max-flow problem, we must be able to push flow forward, but we must also be able to **undo** previous choices if they turn out to be sub-optimal. This is achieved using the **Residual Network** ($G_f$).

For a given graph $G$ and flow $f$, the residual network $G_f$ consists of the same nodes but uses **residual capacities** ($c_f$). The residual capacity is the remaining capacity on an edge that can still be pushed:

This capacity formula has an elegant property:

• If an edge has capacity 10 and we push 3 units of flow forward, the **forward residual capacity** is $10 - 3 = 7$. We can still push 7 more units.
• Due to skew symmetry, the flow in the opposite direction is $-3$. The **backward residual capacity** is $c_f(v, u) = c(v, u) - f(v, u) = 0 - (-3) = 3$. This backward capacity represents our ability to "push back" or cancel up to 3 units of flow we previously sent.

Augmenting Paths

An **Augmenting Path** is a simple directed path from the source $s$ to the sink $t$ in the residual network $G_f$, where every edge along the path has a residual capacity greater than zero ($c_f(u, v) > 0$).

The maximum amount of flow we can push along an augmenting path $p$ is called the **bottleneck capacity** ($c_f(p)$), which is determined by the edge with the smallest residual capacity on the path:

3. Visualizing Network Flow and Residuals

Below is a simple flow network. The edges display `flow / capacity`:

*Mermaid Diagram: A basic network representation showing flow conservation and capacity states.

4. Ford-Fulkerson vs. Edmonds-Karp

The Ford-Fulkerson method is a general framework:

Because it does not specify *how* to find the augmenting path, its worst-case complexity can be poor. If we use Depth-First Search (DFS) to find paths, and the capacities are very large integers, the algorithm might push only 1 unit of flow at a time, resulting in $O(E \cdot f^*)$ operations (where $f^*$ is the maximum flow value).

To solve this, Jack Edmonds and Richard Karp proposed the **Edmonds-Karp Algorithm** (1972). It specifies that augmenting paths must be found using **Breadth-First Search (BFS)**. This simple rule guarantees that we always choose the path with the fewest number of edges.

By choosing the shortest path, Edmonds-Karp bounds the number of augmentations to $O(VE)$, yielding a strict worst-case complexity of **$O(VE^2)$**, regardless of capacity values!

5. Complete Reference Implementation: Python

Here is a complete C-style equivalent Python implementation of the Edmonds-Karp algorithm. It uses BFS to find augmenting paths and maintains parent pointers to reconstruct the path:

6. The Max-Flow Min-Cut Theorem

Why does finding augmenting paths eventually yield the *maximum* possible flow? The mathematical proof relies on the **Max-Flow Min-Cut Theorem**.

An **$s-t$ Cut** partitions the vertices of the graph into two sets, $S$ and $T$, such that the source $s \in S$ and the sink $t \in T$. The **capacity of the cut** is the sum of the capacities of all edges crossing from $S$ to $T$:

The theorem states that:

The value of a maximum flow in a network is equal to the capacity of the minimum cut.

When the algorithm terminates, there are no more augmenting paths from $s$ to $t$ in the residual graph $G_f$. If we group all nodes reachable from $s$ in $G_f$ into set $S$, and all unreachable nodes into set $T$, we form a cut. Since there are no edges with residual capacity crossing from $S$ to $T$ in $G_f$, the flow passing through this cut must equal its capacity, proving we have reached the maximum possible flow!

7. Performance Metrics and Scale

Let us compare how the different variations of network flow algorithms scale with graph complexity:

8. Interactive Max Flow Simulator

Use the simulator below to trace the execution of the Edmonds-Karp algorithm. You can trigger a path search (BFS) and push flow to watch capacities update:

9. Mathematical Proof of Edmonds-Karp Complexity

To prove why the Edmonds-Karp BFS variation guarantees a worst-case runtime of $O(VE^2)$, we must establish the **Monotonic Shortest Path Property**.

Let $\delta_f(s, v)$ denote the shortest path distance (in terms of number of edges) from the source $s$ to a vertex $v$ in the residual graph $G_f$.

Theorem: During the execution of the Edmonds-Karp algorithm, for all vertices $v \in V \setminus \{s, t\}$, the shortest-path distance $\delta_f(s, v)$ in the residual network $G_f$ increases monotonically with each flow augmentation.

Proof Sketch: Suppose a flow augmentation occurs, transforming flow $f$ to $f'$. Assume for contradiction that there exists a vertex $v$ whose distance decreases, i.e., $\delta_{f'}(s, v) < \delta_f(s, v)$. Let $v$ be the closest such vertex to the source in $G_{f'}$, and let $u$ be the predecessor of $v$ on the shortest path from $s$ to $v$.

Because $u$ is closer to the source than $v$, its distance did not decrease:

If the edge $(u, v)$ was in $G_f$ when flow was $f$, then:

This contradicts our assumption that $\delta_{f'}(s, v) < \delta_f(s, v)$. Therefore, the edge $(u, v)$ must NOT have been in $G_f$. This means the augmentation along path $p$ pushed flow from $v$ to $u$, which created the reverse edge $(u, v)$ in the residual graph.

Since the path $p$ was a shortest path in $G_f$, we have:

Combining these equations yields:

Which contradicts the assumption. Thus, shortest-path distances never decrease.

An edge $(u, v)$ is called **critical** during an augmentation if it is the bottleneck edge. Each time an edge becomes critical, it is removed from the residual graph. For $(u, v)$ to become critical again, its distance must increase by at least 2. Since the maximum distance is $|V| - 1$, any single edge can become critical at most $|V|/2$ times. Since there are $|E|$ edges, the total number of flow augmentations is bounded by $O(VE)$. Because each BFS traversal takes $O(E)$ time, the total complexity is:

10. Advanced Network Flow Paradigms

10.1 Dinic's Algorithm

Dinic's algorithm (1970) optimizes Edmonds-Karp by introducing the concept of a **Level Graph** and **Blocking Flows**.

Instead of finding a single shortest path using BFS and updating the graph immediately, Dinic's:

1. Runs a BFS to construct a "Level Graph", where each node is grouped into levels based on its shortest distance from the source.
2. Runs a Depth-First Search (DFS) on this level graph to find a "blocking flow"—pushing multiple paths of flow simultaneously along edges that move strictly from level $L$ to $L+1$.
3. Rebuilds the level graph and repeats until the sink is unreachable.

Dinic's algorithm reduces the worst-case runtime to **$O(V^2E)$**. On unit networks (where capacities are all 1), it runs in $O(E\sqrt{V})$ time, making it exceptionally fast for bipartite matching problems.

10.2 Push-Relabel Algorithm

Unlike Ford-Fulkerson, which maintains a valid flow at every step and searches for global paths, the **Push-Relabel Algorithm** (Goldberg-Tarjan, 1986) works locally. It relaxes the flow conservation constraint, allowing nodes to temporarily hold an "excess" of incoming flow (creating a **preflow**).

Each node is assigned a "height" label. Flow can only be pushed downhill (from a node of height $H$ to a node of height $H-1$). If a node has excess flow but no downhill neighbors, it is **relabeled** (its height is increased by 1).

This localized approach avoids expensive global path searches, yielding a worst-case complexity of **$O(V^3)$** or **$O(V^2\sqrt{E})$** with optimizations, which is highly suited for dense networks.

11. Real-World Applications and Reductions

Many complex scheduling and assignment problems can be reduced to Maximum Flow:

• Bipartite Matching: Suppose you have $N$ jobs and $M$ applicants, where each applicant is qualified for a subset of jobs. How do you maximize the total number of hires?
  Reduction: Create a source node $S$ connected to all applicants (capacity 1) and a sink $T$ connected to all jobs (capacity 1). Add directed edges of capacity 1 from applicants to their qualified jobs. The maximum flow value equals the maximum matching size.
• Image Segmentation (GrabCut): How does a computer determine which pixels belong to the foreground subject and which belong to the background?
  Reduction: Model pixels as graph nodes. Connect adjacent pixels with edges whose capacities represent pixel similarity (edges between similar colors have high capacities). Connect every pixel to a source node (the "foreground" seed) and a sink node (the "background" seed). Finding the minimum cut partitions the pixels, segmenting the image along natural color boundaries.

12. Developer Pitfalls and Guardrails

• Trap: The Infinite Loop on Irrationals. If capacities are irrational numbers, the standard Ford-Fulkerson method (using DFS) might not terminate, and its flow value may converge to a value different from the actual maximum.
  Guardrail: Always use Edmonds-Karp (BFS) or Dinic's algorithm to guarantee termination.
• Trap: Missing Reverse Edges. A common bug when writing max flow is forgetting to add the reverse edge with 0 capacity. Without it, the algorithm cannot push backward flow, preventing it from correcting sub-optimal choices and finding the true maximum flow.
  Guardrail: When parsing input graphs, always initialize a zero-capacity backward edge for every directed edge.

13. Frequently Asked Questions (FAQ)