Network Flow & Max-Cut theory

A Flow Network is a directed graph G = (V, E) utilized to model the transportation of material, data, or energy through a capacitated network. Formally, a flow network is characterized by three mathematical components:

1. A directed graph G = (V, E) with vertex set V and directed edge set E.

2. A non-negative Capacity Function c: V × V → ℝ⁺ ∪ {0}, where c(u, v) ≥ 0 represents the maximum throughput capacity of edge (u, v). If (u, v) ∉ E, then c(u, v) = 0.

3. Two distinguished terminal vertices: a Source vertex s ∈ V (where net flow originates) and a Sink vertex t ∈ V (where net flow terminates), with s ≠ t.



A valid Flow in G is a real-valued function f: V × V → ℝ that strictly satisfies two fundamental physical axioms for all vertices u, v ∈ V:

- Capacity Constraint: For every edge (u, v) ∈ E, the flow cannot exceed available capacity and cannot be negative: 0 ≤ f(u, v) ≤ c(u, v).

- Flow Conservation (Kirchhoff's First Law): For every intermediate vertex u ∈ V \ {s, t}, total incoming flow must strictly equal total outgoing flow:

∑_{v ∈ V} f(v, u) = ∑_{w ∈ V} f(u, w)

Intermediate vertices cannot generate, destroy, or accumulate flow; all fluid entering a junction must exit it.



The Net Value of the flow, denoted |f|, is defined as the total net flow exiting the source vertex (which, by conservation, identically equals total net flow entering the sink):

|f| = ∑_{v ∈ V} f(s, v) - ∑_{v ∈ V} f(v, s)

The Maximum Flow Problem is the optimization objective of finding a flow f* that maximizes |f| subject to the capacity and conservation constraints.



The profound conceptual breakthrough of Lester Ford and Delbert Fulkerson (1956) was the introduction of the Residual Graph G_f = (V, E_f). Given a network G and a flow f, the residual graph represents the additional capacity available to route more flow. For any pair of vertices u, v ∈ V, the Residual Capacity c_f(u, v) is defined as:

c_f(u, v) = c(u, v) - f(u, v) [if (u, v) ∈ E: forward residual capacity]

c_f(u, v) = f(v, u) [if (v, u) ∈ E: backward residual capacity]



The presence of Backward Edges (with residual capacity c_f(u, v) = f(v, u)) is the foundational cornerstone of all augmenting path algorithms. When an augmenting path sends Δ units of flow along a backward edge (u, v) in G_f, it decreases f(v, u) by Δ in the original network! This provides an exact mathematical mechanism to 'cancel' or 'redirect' a sub-optimal flow routing decision made in an earlier iteration. Without backward residual edges, greedy flow routing would become trapped in local sub-optimal dead ends.

The Ford-Fulkerson Method (1956) is an iterative algorithmic framework that computes the maximum flow in a capacitated network by repeatedly discovering Augmenting Paths in the residual graph until no further paths exist.



1. Algorithmic Mechanics:

- Step 1: Initialize the flow on all edges to zero: f(u, v) = 0 for all (u, v) ∈ E. Consequently, the initial residual graph G_f has c_f(u, v) = c(u, v) and c_f(v, u) = 0.

- Step 2: Search for an Augmenting Path P from source s to sink t in the residual graph G_f. An augmenting path is a simple directed path P = (s = v₀, v₁, v₂, ..., v_k = t) where every directed edge (v_i, v_{i+1}) has strictly positive residual capacity: c_f(v_i, v_{i+1}) > 0.

- Step 3: If an augmenting path P exists, determine its Bottleneck Residual Capacity Δ:

Δ = min_{(u, v) ∈ P} c_f(u, v) > 0

- Step 4: Augment the flow f along path P by pushing Δ units of flow:

- For each forward edge (u, v) ∈ P: increase f(u, v) by Δ.

- For each backward edge (u, v) ∈ P: decrease f(v, u) by Δ.

Update the residual graph G_f accordingly.

- Step 5: Repeat Steps 2–4 until no directed path connects s to t in G_f. The final flow f is the maximum flow f*.



2. The Augmenting Path Theorem:

Ford and Fulkerson proved the fundamental theorem: A flow f in a network G is a maximum flow if and only if there is no augmenting path from s to t in the residual graph G_f.



3. Complexity and the Pathological Failure on Irrational Capacities:

Notice that Ford and Fulkerson described a 'method' rather than a deterministic algorithm, because they left the path-finding subroutine unspecified. If an augmenting path is found using generic Depth-First Search (DFS):

- Integer Capacities: In each augmentation, if capacities are integers, the bottleneck capacity Δ is an integer ≥ 1. Therefore, the flow |f| increases by at least 1 in each step. If |f*| is the maximum flow value, the method terminates in at most |f*| iterations. Because each DFS takes O(|E|) time, the total time complexity is O(|E| · |f*|).

This running time is Pseudo-Polynomial: it depends on the magnitude of the capacity values rather than the number of vertices and edges. If a network contains edges with capacity 10⁹, Ford-Fulkerson can require 2 × 10⁹ iterations!

- Irrational Capacities (The Zwick / Rockafellar Construction): If edge capacities are irrational numbers, arbitrary DFS path choices can cause Ford-Fulkerson to enter an infinite loop of augmentations that converge to a flow value strictly less than the maximum flow! To guarantee strongly polynomial termination, augmenting paths must be selected systematically.

In 1972, Jack Edmonds and Richard Karp resolved the pseudo-polynomial vulnerability of Ford-Fulkerson by introducing a simple yet profound algorithmic rule: always choose the Augmenting Path that has the Minimum Number of Edges. This is accomplished by finding augmenting paths in the residual graph G_f using Breadth-First Search (BFS) rather than DFS.



1. Monotonic Shortest-Path Distance Invariant:

Let δ_f(s, v) denote the Shortest Path Distance (measured as the minimum number of edges) from source s to vertex v in the residual graph G_f.

Edmonds and Karp proved the foundational Monotonicity Lemma: For every vertex v ∈ V \ {s}, the shortest path distance δ_f(s, v) in G_f never decreases after a flow augmentation:

δ_{f'}(s, v) ≥ δ_f(s, v)

where f' is the flow obtained after augmenting along a shortest path P.



Proof by Contradiction:

Suppose for contradiction that there exists some vertex whose distance strictly decreases after augmentation. Let v be a vertex with strictly minimum δ_{f'}(s, v) such that δ_{f'}(s, v) < δ_f(s, v). Let u be the predecessor of v on a shortest path from s to v in G_{f'}, so that δ_{f'}(s, v) = δ_{f'}(s, u) + 1. By the minimality of v, u's distance did not decrease: δ_{f'}(s, u) ≥ δ_f(s, u).

Now consider the residual edge (u, v):

- If (u, v) already existed in G_f prior to augmentation, then δ_f(s, v) ≤ δ_f(s, u) + 1 ≤ δ_{f'}(s, u) + 1 = δ_{f'}(s, v), directly contradicting the assumption that δ_{f'}(s, v) < δ_f(s, v)!

- If (u, v) was not in G_f, it must have been created by the augmentation. But an edge (u, v) is added to G_f only if flow was pushed along reverse edge (v, u) in the augmenting path P, meaning (v, u) was on a shortest path in G_f:

δ_f(s, u) = δ_f(s, v) + 1

Substituting this yields:

δ_f(s, v) = δ_f(s, u) - 1 ≤ δ_{f'}(s, u) - 1 = δ_{f'}(s, v) - 2 < δ_{f'}(s, v)

which again contradicts the assumption! Therefore, distances from s can never decrease.



2. Bounding the Number of Augmentations:

An edge (u, v) on augmenting path P is called a Critical Edge if its residual capacity equals the bottleneck capacity: c_f(u, v) = Δ. Pushing Δ units of flow saturates (u, v), completely removing it from the residual graph G_{f'}.

For (u, v) to become critical again in a later iteration, flow must first be pushed in reverse along (v, u). When (u, v) was critical:

δ_f(s, v) = δ_f(s, u) + 1

When reverse flow was subsequently pushed along (v, u):

δ_{f''}(s, u) = δ_{f''}(s, v) + 1

By the monotonicity lemma, δ_{f''}(s, v) ≥ δ_f(s, v). Therefore:

δ_{f''}(s, u) ≥ δ_f(s, v) + 1 = δ_f(s, u) + 2

Every time edge (u, v) becomes critical, the shortest path distance to u must increase by at least 2 levels! Because shortest path distance from s to u cannot exceed |V| - 2, edge (u, v) can become critical at most (|V| - 2) / 2 + 1 < |V| / 2 times.



Because there are at most 2|E| directed edges in the residual graph, the total number of critical edge saturations—and hence the Total Number of Augmenting Iterations—is strictly bounded by:

Total Augmentations ≤ 2|E| · (|V| / 2) = O(|V| · |E|)

Because each BFS traversal takes O(|E|) time, the total running time of the Edmonds-Karp algorithm is strictly O(|V| · |E|²). This bound is Strongly Polynomial: it depends solely on graph topology (|V| and |E|) and is completely invariant to capacity scales.

The Max-Flow Min-Cut Theorem, independently proven by Lester Ford and Delbert Fulkerson (1956) and Peter Elias, Amiel Feinstein, and Claude Shannon (1956), is one of the foundational duality theorems in applied mathematics and computer science.



1. Definition of a Cut:

Let G = (V, E) be a flow network with source s and sink t. An s-t Cut, denoted (S, T), is a partition of the vertex set V into two disjoint, non-empty subsets S and T = V \ S such that the source belongs to S (s ∈ S) and the sink belongs to T (t ∈ T).

The Capacity of a Cut, denoted c(S, T), is defined strictly as the sum of capacities of all directed edges originating in S and terminating in T:

c(S, T) = ∑_{u ∈ S, v ∈ T} c(u, v)

(Notice that edges directed backwards from T to S do not contribute to cut capacity).



2. The Weak Duality Inequality:

For any arbitrary valid flow f and any arbitrary s-t cut (S, T), the net flow |f| across the cut satisfies:

|f| = ∑_{u ∈ S, v ∈ T} f(u, v) - ∑_{w ∈ T, z ∈ S} f(w, z) ≤ ∑_{u ∈ S, v ∈ T} f(u, v) ≤ ∑_{u ∈ S, v ∈ T} c(u, v) = c(S, T)

Therefore, the value of any valid flow is strictly upper-bounded by the capacity of any valid cut:

|f| ≤ c(S, T) for all flows f and cuts (S, T)

This immediately implies that if |f| = c(S, T), then f is guaranteed to be a Maximum Flow, and (S, T) is guaranteed to be a Minimum Cut!



3. Proof of the Max-Flow Min-Cut Theorem via Residual Reachability:

The theorem states: In any flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut:

max_{f} |f| = min_{(S, T)} c(S, T)



Proof:

Let f* be a flow in G such that the residual graph G_{f*} contains no augmenting path from s to t. We construct a cut (S, T) as follows:

- Let S = {v ∈ V : there exists a directed path from s to v in G_{f*}}

- Let T = V \ S.

By construction:

1. s ∈ S (since s can reach itself with 0 edges).

2. t ∈ T (since by assumption, there is no directed path from s to t in G_{f*}). Therefore, (S, T) is a valid s-t cut.

3. Now examine any pair of vertices u ∈ S and v ∈ T. In the original network G:

- If edge (u, v) ∈ E: we must have f*(u, v) = c(u, v). If f*(u, v) < c(u, v), then residual capacity c_{f*}(u, v) > 0 would exist, meaning v would be reachable from u in G_{f*}, forcing v ∈ S, a contradiction!

- If edge (v, u) ∈ E: we must have f*(v, u) = 0. If f*(v, u) > 0, then reverse residual capacity c_{f*}(u, v) = f*(v, u) > 0 would exist, again forcing v ∈ S, a contradiction!



Evaluating the net flow across this constructed cut:

|f*| = ∑_{u ∈ S, v ∈ T} f*(u, v) - ∑_{v ∈ T, u ∈ S} f*(v, u) = ∑_{u ∈ S, v ∈ T} c(u, v) - 0 = c(S, T)

Since |f*| = c(S, T), weak duality guarantees that f* is a Maximum Flow and (S, T) is a Minimum Cut! The proof is complete.



4. Connection to Linear Programming Duality:

The Maximum Flow problem can be formulated as a Primal Linear Program with flow variables f(u, v) and capacity/conservation constraints. The Dual Linear Program of this formulation assigns potential variables p_u to vertices and shadow prices d(u, v) to edges. By the Strong Duality Theorem of Linear Programming, the optimal objective values of primal and dual are identical. It can be proven that the dual program's optimal integer solutions correspond precisely to the characteristic indicator vectors of an s-t cut, making Max-Flow Min-Cut an exact combinatorial manifestation of LP Strong Duality.

Invented by Soviet mathematician E. A. Dinic in 1970 (and independently rediscovered by Shimon Even and Alon Itai), Dinic's Algorithm revolutionized maximum flow computation by routing flow through multiple augmenting paths simultaneously in a single phase.



1. Algorithmic Phases & Structural Concepts:

While Edmonds-Karp executes a full BFS across the entire graph to discover just one single augmenting path, Dinic decomposes the computation into two hierarchical stages:

- Stage 1: Level Graph Construction (BFS):

Construct the Level Graph G_L of residual network G_f using BFS. For each vertex v, define its level level(v) as the shortest path distance from source s in G_f. Edges in G_L are restricted strictly to admissible edges that advance outward by exactly 1 level:

E_L = { (u, v) ∈ E_f : level(v) = level(u) + 1 and c_f(u, v) > 0 }

G_L is a Directed Acyclic Graph (DAG) with vertices organized into topological tiers.

- Stage 2: Finding a Blocking Flow (DFS):

Within the Level Graph G_L, the algorithm routes a Blocking Flow f_b. A flow f_b in G_L is blocking if every directed path from s to t in G_L contains at least one saturated edge. This is computed efficiently using depth-first search with a Next-Edge pointer optimization (pruning dead-end branches so vertices with zero outgoing capacity are never revisited).

- Stage 3: Phase Termination and Iteration:

Augment flow f with f_b: f ← f + f_b. Reconstruct the residual graph G_f. Repeat Stages 1–3 until sink t is unreachable from s in G_f.



2. Phase Bound & Asymptotic Complexity:

Dinic proved that after each phase, the level of the sink level(t) strictly increases by at least 1: level_{next}(t) ≥ level(t) + 1. Because level(t) is bounded by |V| - 1, there can be at most |V| - 1 phases total!

In each phase:

- Building G_L takes O(|E|) time.

- Finding a blocking flow using DFS with next-edge pointers takes O(|V| · |E|) time (each edge is saturated at most once, and dead-end walks take at most O(|V|) per retreat).

Therefore, the total running time of Dinic's algorithm is:

T(|V|, |E|) = O(|V| phases · |V| · |E|) = O(|V|² · |E|)

This is a dramatic improvement over Edmonds-Karp's O(|V| · |E|²).



3. Super-Efficiency on Unit Networks (O(|E| √|V|)):

On Unit Networks—networks where all capacities are 1, or networks derived from Bipartite Matching where every internal vertex has either in-degree 1 or out-degree 1—Dinic's algorithm runs at breathtaking speed! Shimon Even and Robert Tarjan (1975) proved that on unit networks, after 2√|V| phases, the remaining residual distance to t exceeds √|V|, which mathematically limits the remaining flow to at most O(√|V|). Consequently, the total number of phases is bounded by O(√|V|). Each blocking flow phase on unit networks takes O(|E|) time. Therefore, Dinic computes Maximum Bipartite Matching in strictly O(|E| √|V|) time, matching the theoretical bound of the famous Hopcroft-Karp algorithm while using a general-purpose network flow engine.

All augmenting path algorithms (Ford-Fulkerson, Edmonds-Karp, Dinic) operate under a global paradigm: they maintain strict flow conservation at all intermediate vertices at all times, searching for end-to-end paths from s to t to augment flow. In 1986, Andrew V. Goldberg and Robert E. Tarjan pioneered a radically different paradigm known as the Push-Relabel (or Preflow-Push) Method, which abandons global conservation during execution and operates through purely local vertex updates.



1. Preflow and Excess:

A Preflow is a function f: V × V → ℝ satisfying capacity constraints (0 ≤ f(u, v) ≤ c(u, v)), but relaxing flow conservation to allow net inflow to exceed outflow. For any vertex u ∈ V \ {s}, the Excess e(u) is defined as:

e(u) = ∑_{v ∈ V} f(v, u) - ∑_{w ∈ V} f(u, w) ≥ 0

A vertex u is Active if e(u) > 0. Active vertices act as temporary reservoirs holding excess fluid that must eventually be pushed downhill toward the sink t (or back to the source s).



2. Height Function (Distance Labels):

Each vertex u is assigned an integer Height (or distance label) h(u). A height function is Valid if:

- h(s) = |V| and h(t) = 0 (the source sits at elevation |V|; the sink sits at elevation 0).

- For every residual edge (u, v) ∈ E_f, h(u) ≤ h(v) + 1 (fluid can only flow downhill or horizontally; it cannot flow uphill across steep cliffs).



3. Fundamental Operations:

Push-Relabel maintains a preflow and a valid height function, executing two local operations on active vertices:

- Operation 1: Push(u, v) (Applicable when u is active, c_f(u, v) > 0, and h(u) = h(v) + 1):

Pushes Δ = min(e(u), c_f(u, v)) units of fluid from reservoir u downhill to neighbor v. If Δ = c_f(u, v), the push is Saturating; otherwise it is Non-Saturating.

- Operation 2: Relabel(u) (Applicable when u is active and for all residual neighbors v with c_f(u, v) > 0, h(u) ≤ h(v)):

When an active vertex cannot push fluid to any neighbor because all neighbors are at the same or higher elevation, it increases its elevation to allow downhill flow:

h(u) = 1 + min { h(v) : (u, v) ∈ E_f }



4. Algorithmic Execution & Asymptotic Bound:

Initialization saturates all edges leaving source s (f(s, v) = c(s, v)), setting h(s) = |V| and h(v) = 0 for all v ≠ s. The algorithm maintains an active queue of vertices with e(u) > 0, repeatedly executing Push and Relabel operations until no active vertices remain (all excess has either reached sink t or been pushed back to source s).

Goldberg and Tarjan proved that heights never exceed 2|V| - 1. There are at most O(|V|²) relabel operations and at most O(|V| · |E|) saturating pushes. Using the FIFO vertex selection rule, non-saturating pushes are bounded by O(|V|³), yielding a total time complexity of O(|V|³). With dynamic trees (Sleator and Tarjan), Push-Relabel achieves O(|V| · |E| log(|V|² / |E|)). The primary microarchitectural advantage of Push-Relabel is its embarrassingly parallel structure: active vertices can discharge fluid completely locally, making Push-Relabel the algorithm of choice for multi-core and GPU flow accelerators.

Maximum Flow and the Max-Flow Min-Cut Theorem are not merely abstract graph exercises; they serve as a universal reduction framework for solving complex discrete optimization problems across computer science, operations research, computer vision, and systems engineering.



1. Maximum Bipartite Matching:

Given a bipartite graph G = (L ∪ R, E) where edges exist only between disjoint sets L and R, a Matching is a subset of edges sharing no common vertices. We reduce this to Max-Flow via the canonical transformation:

- Add a super-source s and connect s to every vertex u ∈ L with capacity c(s, u) = 1.

- Direct all original bipartite edges from u ∈ L to v ∈ R with capacity c(u, v) = 1 (or ∞).

- Add a super-sink t and connect every vertex v ∈ R to t with capacity c(v, t) = 1.

By the Integrality Theorem (if capacities are integers, maximum flow is integral), every edge carries either 0 or 1 unit of flow. Flow conservation ensures each left vertex and right vertex is matched at most once. The maximum flow value |f*| strictly equals the maximum bipartite matching cardinality, and the minimum cut identifies the minimum vertex cover (König's Theorem)!



2. Edge-Disjoint and Vertex-Disjoint Paths (Menger's Theorem):

Karl Menger (1927) proved that the maximum number of edge-disjoint paths connecting s to t equals the minimum number of edges whose removal disconnects s from t. By assigning unit capacity c(e) = 1 to every edge, the maximum flow |f*| directly computes the maximum number of edge-disjoint routing paths, foundational to fault-tolerant telecommunications network routing.



3. Computer Vision: Image Segmentation via Graph Cuts (Boykov-Kolmogorov):

In image processing, segmentation partitions pixels into Foreground and Background. This is formulated as an energy minimization problem over a Markov Random Field (MRF):

E(x) = ∑_{p} D_p(x_p) + ∑_{(p, q)} V_{pq}(x_p, x_q)

where D_p represents the pixel color likelihood cost and V_{pq} represents boundary smoothness. By constructing a graph where source s represents Foreground, sink t represents Background, terminal edge capacities represent likelihoods D_p, and neighboring pixel edges represent smoothness penalties V_{pq}, the exact global minimum energy segmentation is computed in polynomial time as the Minimum s-t Cut! This powers medical MRI organ segmentation, interactive image cutout tools (Photoshop Magic Wand), and stereo depth estimation.



4. Project Selection (Open-Pit Mining Problem):

Given a set of projects P where project i yields revenue p_i > 0 or incurs cost p_i < 0, subject to prerequisite precedence dependencies (project i requires project j), find a feasible subset maximizing total profit. By constructing a flow network with capacities c(s, i) = p_i for positive projects, c(j, t) = -p_j for negative projects, and dependency edges with capacity ∞, the minimum cut partitions V such that total revenue minus cost is maximized in O(|V| · |E|²) time.