Network Flow

Why this problem exists (motivation)

Many optimization problems on graphs are about routes (shortest path), orderings (topological constraints), or structures (spanning trees). Network flow is different: it is about simultaneous movement through many edges at once, where each edge has a limited capacity.

Think of a directed graph as a pipe network:

• •Vertices are junctions.
• •Edges are pipes.
• •Capacities are how much can pass through a pipe per unit time.
• •A source $s$ injects flow; a sink $t$ absorbs it.

The core question:

What is the maximum amount of flow that can be sent from $s$ to $t$ without violating edge capacities?

Formal definition: flow network

A flow network is a directed graph $G = (V,E)$ with:

• •a source $s \in V$
• •a sink $t \in V$
• •a capacity function $c: E \to \mathbb{R}_{\ge 0}$, where $c(u,v)$ is the capacity of edge $(u,v)$

We allow the convention that if $(u,v) \notin E$, then $c(u,v)=0$.

Feasible $s$–$t$ flow

A flow is a function $f: V \times V \to \mathbb{R}$ (often only nonzero on edges), interpreted as $f(u,v)$ = amount sent on edge $(u,v)$.

A flow is feasible if it satisfies:

1) Capacity constraints (can’t exceed the pipe):

• •For every $(u,v)$,

2) Flow conservation (what goes in must go out) for every intermediate vertex $v \in V \setminus \{s,t\}$:

Let incoming flow to $v$ be $\sum_{u \in V} f(u,v)$ and outgoing be $\sum_{w \in V} f(v,w)$. Then

Equivalently, net flow at $v$ is zero.

3) Value of the flow (objective):

The amount successfully sent from $s$ to $t$ is

In many treatments we assume no edges enter $s$ and no edges leave $t$, making this simply $|f| = \sum_{v} f(s,v)$.

Connection to linear programming (you already know this)

Max flow is a linear program:

• •Variables: $f(u,v)$
• •Constraints: capacity bounds and conservation
• •Objective: maximize $|f|$

That matters because it hints at:

• •Why a theorem like max-flow min-cut could hold (duality flavor)
• •Why integral capacities often lead to integral optimal flows (totally unimodular structure)

But the network-flow viewpoint gives more than “solve an LP”: it gives a combinatorial algorithm and a geometric intuition.

The other side of the coin: cuts

A cut feels like a “barrier” rather than a “routing.” Yet it pins down the answer.

An $s$–$t$ cut is a partition of vertices into two sets $(S,T)$ such that:

• •$s \in S$
• •$t \in T$
• •$S \cup T = V$, $S \cap T = \emptyset$

The capacity of the cut is the total capacity of edges going from $S$ to $T$:

Intuition: if you draw a boundary around $S$, the only way flow can go from $s$ to $t$ is to cross from $S$ to $T$. Those crossing edges limit the total possible flow.

We will later prove:

That equality is the Max-Flow Min-Cut Theorem—the central result of this node.

Why we need residual networks

Suppose you have some feasible flow $f$. You want to increase it.

If an edge $(u,v)$ has unused capacity, you can push more forward.

But you also want the ability to change your mind: if later you discover that flow you sent earlier blocks a better routing, you’d like to pull some flow back and reroute it elsewhere.

Residual networks encode both possibilities:

• •remaining forward capacity
• •reversible capacity (send flow “backward” to undo)

This is what makes Ford–Fulkerson work.

Residual capacity

Given a capacity $c(u,v)$ and current flow $f(u,v)$, the forward residual capacity is:

If $c_f(u,v) > 0$, you can increase $f(u,v)$.

Now the crucial twist: if $f(u,v) > 0$, you can decrease it by sending flow in the reverse direction. That creates a backward edge $(v,u)$ in the residual graph with residual capacity:

This is not a real physical edge in the original network; it represents “canceling” previously sent flow.

Residual network $G_f$

The residual network $G_f = (V, E_f)$ contains all directed edges with positive residual capacity:

• •include $(u,v)$ if $c_f(u,v) > 0$

Each such edge has capacity $c_f(u,v)$.

Augmenting path

An augmenting path is any directed path from $s$ to $t$ in the residual network $G_f$.

If you can find one, you can increase the total flow value.

Let $P$ be an augmenting path. The maximum amount you can push through it is limited by the smallest residual capacity along it:

This $\Delta$ is called the bottleneck of the path.

How augmentation updates the flow

For each edge $(u,v)$ on the path $P$:

• •If $(u,v)$ is a forward edge of the original direction, do

• •If $(u,v)$ is a backward residual edge (meaning original had flow from $v$ to $u$), do

This preserves feasibility:

• •Capacity bounds: we never exceed because $\Delta \le c_f(u,v)$
• •Conservation: along the internal vertices of the path, what you add in equals what you add out (a telescoping effect)

Diagram 1: Residual forward and backward edges (static SVG)

The picture below shows one original edge and the residual edges it induces.

<svg xmlns="http://www.w3.org/2000/svg" width="820" height="230" viewBox="0 0 820 230" role="img" aria-label="Residual network illustration showing forward residual capacity and backward residual edge for canceling flow">
  <defs>
    <marker id="arrow" markerWidth="10" markerHeight="10" refX="10" refY="3" orient="auto" markerUnits="strokeWidth">
      <path d="M0,0 L10,3 L0,6 Z" fill="#222" />
    </marker>
    <marker id="arrowBlue" markerWidth="10" markerHeight="10" refX="10" refY="3" orient="auto" markerUnits="strokeWidth">
      <path d="M0,0 L10,3 L0,6 Z" fill="#1f77b4" />
    </marker>
    <marker id="arrowRed" markerWidth="10" markerHeight="10" refX="10" refY="3" orient="auto" markerUnits="strokeWidth">
      <path d="M0,0 L10,3 L0,6 Z" fill="#d62728" />
    </marker>
  </defs>

  <!-- Nodes -->
  <circle cx="170" cy="115" r="28" fill="#fff" stroke="#222" stroke-width="2" />
  <text x="170" y="121" text-anchor="middle" font-family="sans-serif" font-size="16">u</text>

  <circle cx="650" cy="115" r="28" fill="#fff" stroke="#222" stroke-width="2" />
  <text x="650" y="121" text-anchor="middle" font-family="sans-serif" font-size="16">v</text>

  <!-- Original edge -->
  <line x1="198" y1="115" x2="622" y2="115" stroke="#222" stroke-width="3" marker-end="url(#arrow)" />
  <text x="410" y="90" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#222">original edge (u→v)</text>
  <text x="410" y="136" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#222">capacity c(u,v)=10, current flow f(u,v)=6</text>

  <!-- Residual forward -->
  <line x1="210" y1="55" x2="610" y2="55" stroke="#1f77b4" stroke-width="3" marker-end="url(#arrowBlue)" />
  <text x="410" y="40" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#1f77b4">forward residual: c_f(u,v)=c-f=4</text>

  <!-- Residual backward -->
  <line x1="610" y1="175" x2="210" y2="175" stroke="#d62728" stroke-width="3" marker-end="url(#arrowRed)" />
  <text x="410" y="200" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#d62728">backward residual: c_f(v,u)=f=6 (can cancel)</text>

  <text x="410" y="18" text-anchor="middle" font-family="sans-serif" font-size="16" fill="#222">Residual edges represent “can add” and “can undo”</text>
</svg>

A small but important conceptual pause

Residual edges are often the hardest part to internalize. Two reminders help:

1) Backward residual edges do not violate the original graph direction. They are bookkeeping that says: “you may reduce the earlier decision.”

2) Augmenting along a residual path may mix forward and backward edges. That corresponds to a rerouting: some flow gets pushed into a new corridor, and some earlier corridor gets partially emptied.

Why augmenting paths increase flow value

Let $P$ be an $s \to t$ path and augment by $\Delta$.

• •At $s$, you increase net outgoing by $\Delta$.
• •At $t$, you increase net incoming by $\Delta$.
• •At internal vertices, increases cancel (one edge adds $\Delta$ in, another adds $\Delta$ out).

So:

That’s the engine of Ford–Fulkerson.

The algorithm idea (why before how)

We want maximum flow. Instead of guessing a final flow, we:

1) start with zero flow

2) repeatedly find a way to push more (augmenting path)

3) stop when no improvement is possible

This is a classic “local improvement” strategy, except the residual network is designed so that “no local improvement” actually implies “global optimum.”

Ford–Fulkerson method (high-level)

Initialize $f(u,v)=0$ for all edges.

Repeat:

• •Construct residual graph $G_f$
• •Find any $s$–$t$ path $P$ in $G_f$
• •Let $\Delta = \min_{(u,v) \in P} c_f(u,v)$
• •Augment along $P$ by $\Delta$

Stop when no augmenting path exists.

Pseudocode (conceptual)

• •While there exists an augmenting path $P$ in $G_f$:
• •$\Delta \leftarrow \min$ residual capacity on $P$
• •For each edge $(u,v)$ on $P$:
• •if $(u,v)$ is a forward residual edge: $f(u,v) \leftarrow f(u,v) + \Delta$
• •else (backward): $f(v,u) \leftarrow f(v,u) - \Delta$

Termination: integer capacities vs. real capacities

This is a subtle point, and it’s important at difficulty 4.

• •If all capacities are integers, and we always augment by the bottleneck $\Delta$, then $\Delta$ is an integer, and the flow value increases by at least 1 each augmentation. Since the max flow value is at most the total capacity leaving $s$, the algorithm must terminate.

• •If capacities are rational, scaling them by a common denominator reduces to the integer case.

• •If capacities are real, naive Ford–Fulkerson can fail to terminate (it can keep making smaller and smaller improvements).

So, for guaranteed polynomial-time behavior, we specify a strategy for picking augmenting paths.

Edmonds–Karp (a canonical path strategy)

Edmonds–Karp is Ford–Fulkerson where the augmenting path is chosen as the shortest path in number of edges in the residual graph (use BFS).

Key facts:

• •It always terminates.
• •Running time is $O(VE^2)$.

Even if you don’t memorize the proof, the intuition is useful:

• •Shortest augmenting paths tend not to “thrash” back and forth.
• •Distances (layer levels) from $s$ in the residual graph can only increase a bounded number of times before edges become permanently saturated in a way that prevents them from reappearing on short paths.

Complexity comparison table

A careful note about representation

When implementing, you almost always store:

• •adjacency list of residual edges
• •current residual capacities
• •pointers to reverse edges (so updates are $O(1)$)

Even if the original graph has only forward edges, the residual graph will contain backward edges during the run.

Integrality (why flows are often integers)

If all capacities are integers, maximum flow has an optimal solution with integer flows.

Reason (informal but accurate):

• •With Edmonds–Karp, each augmentation pushes an integer bottleneck
• •Starting at 0, all flows remain integers

This is extremely powerful: it turns many “counting” problems into flow problems (matchings, disjoint paths, bipartite assignment variants).

Why the theorem matters

Ford–Fulkerson gives you a flow. But how do you know it’s optimal?

Max-Flow Min-Cut gives a crisp certificate:

• •A flow value can never exceed the capacity of any cut.
• •When the algorithm stops, we can build a cut whose capacity equals the current flow value.

So you get both:

• •an optimal value
• •a proof of optimality (the min cut)

Step 1: Any flow is bounded by any cut

Take any feasible flow $f$ and any cut $(S,T)$.

Consider net flow leaving $S$:

Because every vertex in $S$ except possibly $s$ has flow conservation, all internal cancellations happen, and the expression collapses to $|f|$ (the only net source inside $S$ is $s$).

More directly, one can show:

Now use bounds:

• •$f(u,v) \le c(u,v)$ on edges from $S$ to $T$
• •$f(u,v) \ge 0$ on edges from $T$ to $S$

So:

This implies:

So the max flow is always ≤ min cut capacity.

Step 2: When no augmenting path exists, a cut “falls out”

Assume Ford–Fulkerson has stopped: there is no $s \to t$ path in residual graph $G_f$.

Let $S$ be the set of vertices reachable from $s$ in $G_f$ (including $s$). Let $T = V \setminus S$.

Because $t$ is not reachable, we have $t \in T$. Thus $(S,T)$ is a valid cut.

Now consider any original edge $(u,v)$ with $u \in S$ and $v \in T$.

Claim: this edge must be saturated:

Why? If it were not saturated, then forward residual capacity would be positive:

meaning $(u,v)$ would appear in $G_f$, and then $v$ would be reachable from $u$ (and from $s$), contradicting $v \in T$.

So every edge from $S$ to $T$ is saturated.

Also consider any original edge $(v,u)$ from $T$ to $S$ (opposite direction). Claim: it must carry zero flow:

Why? If $f(v,u) > 0$, then the backward residual edge $(u,v)$ would have positive residual capacity $c_f(u,v)=f(v,u)$, making $v$ reachable from $u$ and hence from $s$, again contradicting $v \in T$.

Step 3: The cut capacity equals the flow value

Compute $|f|$ using the cut identity:

But we just established:

• •for $S \to T$ edges: $f(u,v)=c(u,v)$
• •for $T \to S$ edges: $f(u,v)=0$

So:

Thus the current flow equals the capacity of this cut.

Combine with Step 1:

• •$|f| \le \min c(S,T)$ for any flow
• •we found a cut with $c(S,T) = |f|$

Therefore $f$ is maximum and $(S,T)$ is a minimum cut:

Diagram 2: Reachable set S vs T defines the min cut (static SVG)

This diagram shows a residual graph situation at termination: vertices reachable from $s$ are shaded as $S$; $t$ is in $T$. All edges from $S$ to $T$ are saturated (no forward residual capacity), so there is no crossing residual edge.

<svg xmlns="http://www.w3.org/2000/svg" width="880" height="320" viewBox="0 0 880 320" role="img" aria-label="Cut from reachable set in residual network: S is reachable from s, T contains t, and edges from S to T are saturated">
  <defs>
    <marker id="arr" markerWidth="10" markerHeight="10" refX="10" refY="3" orient="auto" markerUnits="strokeWidth">
      <path d="M0,0 L10,3 L0,6 Z" fill="#222" />
    </marker>
  </defs>

  <!-- Background regions -->
  <rect x="20" y="40" width="400" height="250" fill="#e8f4ff" stroke="#1f77b4" stroke-width="2"/>
  <rect x="460" y="40" width="400" height="250" fill="#fff0f0" stroke="#d62728" stroke-width="2"/>
  <text x="220" y="30" text-anchor="middle" font-family="sans-serif" font-size="16" fill="#1f77b4">S (reachable from s in residual)</text>
  <text x="660" y="30" text-anchor="middle" font-family="sans-serif" font-size="16" fill="#d62728">T (not reachable)</text>

  <!-- Nodes in S -->
  <circle cx="120" cy="110" r="22" fill="#fff" stroke="#222" stroke-width="2"/>
  <text x="120" y="116" text-anchor="middle" font-family="sans-serif" font-size="14">s</text>

  <circle cx="240" cy="110" r="22" fill="#fff" stroke="#222" stroke-width="2"/>
  <text x="240" y="116" text-anchor="middle" font-family="sans-serif" font-size="14">a</text>

  <circle cx="180" cy="210" r="22" fill="#fff" stroke="#222" stroke-width="2"/>
  <text x="180" y="216" text-anchor="middle" font-family="sans-serif" font-size="14">b</text>

  <!-- Nodes in T -->
  <circle cx="600" cy="110" r="22" fill="#fff" stroke="#222" stroke-width="2"/>
  <text x="600" y="116" text-anchor="middle" font-family="sans-serif" font-size="14">c</text>

  <circle cx="720" cy="210" r="22" fill="#fff" stroke="#222" stroke-width="2"/>
  <text x="720" y="216" text-anchor="middle" font-family="sans-serif" font-size="14">t</text>

  <!-- Residual edges inside S (reachable) -->
  <line x1="142" y1="110" x2="218" y2="110" stroke="#222" stroke-width="2.5" marker-end="url(#arr)"/>
  <text x="180" y="96" text-anchor="middle" font-family="sans-serif" font-size="12">residual&gt;0</text>

  <line x1="130" y1="126" x2="170" y2="190" stroke="#222" stroke-width="2.5" marker-end="url(#arr)"/>

  <line x1="220" y1="126" x2="195" y2="188" stroke="#222" stroke-width="2.5" marker-end="url(#arr)"/>

  <!-- Original edges from S to T are saturated => show as dashed and labeled saturated -->
  <line x1="262" y1="110" x2="578" y2="110" stroke="#222" stroke-width="3" stroke-dasharray="6,6" marker-end="url(#arr)"/>
  <text x="420" y="100" text-anchor="middle" font-family="sans-serif" font-size="12">S→T edge saturated (no residual)</text>

  <line x1="202" y1="210" x2="705" y2="210" stroke="#222" stroke-width="3" stroke-dasharray="6,6" marker-end="url(#arr)"/>
  <text x="455" y="200" text-anchor="middle" font-family="sans-serif" font-size="12">S→T edge saturated (no residual)</text>

  <!-- Edges inside T (may exist, but unreachable from s) -->
  <line x1="620" y1="126" x2="705" y2="194" stroke="#222" stroke-width="2" marker-end="url(#arr)"/>
  <text x="690" y="150" text-anchor="middle" font-family="sans-serif" font-size="12">(unreached)</text>

  <!-- Label: cut boundary -->
  <text x="440" y="285" text-anchor="middle" font-family="sans-serif" font-size="14">Cut boundary between S and T</text>
</svg>

Practical payoff: you get a minimum cut for free

From the final residual graph you can extract:

• •$S$ = reachable from $s$ via residual edges
• •the min-cut edges are exactly original edges $(u,v)$ with $u \in S$, $v \in T$

This is extremely useful in applications (segmentation, clustering, reliability, identifying bottlenecks) because the min cut provides interpretability: “here are the edges that truly limit throughput.”