Network Flow — Conceptual Introduction

Imagine you're the chief engineer of a water distribution company. You have a massive network of pipes connecting a reservoir (your source) to a city's water treatment facility (your sink). Each pipe has a maximum capacity—it can only carry so much water per second before the pressure becomes dangerous. Your mission: determine the maximum amount of water you can push through this network from source to sink.

This seemingly simple question—how much can flow?—is the essence of the Maximum Flow Problem, one of the most elegant and powerful optimization frameworks in computer science. Far from being merely about water or pipes, the maximum flow problem captures the mathematical structure underlying countless real-world optimization challenges.

Let's ground our intuition with mathematical precision. The Maximum Flow Problem is defined on a special type of directed graph called a flow network.

Formal Definition:

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

1. Source vertex (s): A distinguished vertex with no incoming edges (or where we ignore incoming edges). All flow originates here.

2. Sink vertex (t): A distinguished vertex with no outgoing edges (or where we ignore outgoing edges). All flow terminates here.

3. Capacity function c: Each edge (u, v) ∈ E has an associated capacity c(u, v) ≥ 0, representing the maximum flow that can traverse that edge.

4. Flow function f: An assignment of flow values to edges, where f(u, v) represents the actual flow from u to v.

The Constraints a Valid Flow Must Satisfy:

For a flow function f to be valid, it must satisfy two fundamental constraints:

1. Capacity Constraint (Don't Overflow):

For every edge (u, v) ∈ E:

$$0 \leq f(u, v) \leq c(u, v)$$

The flow on each edge must be non-negative and cannot exceed the edge's capacity. You can't push more water through a pipe than the pipe can handle, and flow doesn't go backward spontaneously.

2. Flow Conservation (What Goes In Must Come Out):

For every vertex v ∈ V except s and t:

$$\sum_{u \in V} f(u, v) = \sum_{w \in V} f(v, w)$$

The total flow entering any intermediate vertex must equal the total flow leaving it. Flow doesn't accumulate or disappear at intermediate nodes—like water through a pipe network, what enters a junction must exit.

Abstract definitions become concrete through visualization. Let's examine a simple flow network to build intuition.

Consider this network:

         [A]----10--->[C]
        ↗    ↘       ↗    ↘
       8      4     6      8
      ↗        ↘   ↗        ↘
    [S]         [B]----5---->[T]
      ↘        ↗   ↘        ↗
       6      3     4      9
        ↘    ↗       ↘    ↗
         [D]----7--->[E]

Here, S is the source, T is the sink, and the numbers represent edge capacities. The vertices A, B, C, D, E are intermediate nodes through which flow is routed.

Key Observations:

1. Multiple paths exist from S to T (S→A→C→T, S→B→T, S→D→E→T, etc.)
2. Bottlenecks matter — even if S→A has capacity 8 and A→C has capacity 10, we can only push 8 units through this path segment
3. Flow can split and merge — flow from S can go through multiple vertices and recombine before reaching T

A Simple Example with Numbers:

Consider the simplest non-trivial network:

    [S] ---10---> [A] ---5---> [T]

The maximum flow here is 5, not 10, because the bottleneck edge (A→T) limits total throughput. Even though we can push 10 units from S to A, only 5 can continue to T.

Now consider a slightly more complex case:

         ----10----
        /          
      [S]           [T]
        \          /
         ----8-----

With two parallel edges from S to T with capacities 10 and 8, the maximum flow is 10 + 8 = 18. The paths don't share edges, so their capacities add directly.

The complexity arises when paths share edges—this is where naive approaches fail and sophisticated algorithms become necessary.

The maximum flow problem isn't merely an academic curiosity—it models an extraordinary range of practical optimization problems. Understanding why this formulation is so powerful reveals the deep structure underlying seemingly unrelated domains.

The Computational Perspective:

From a complexity standpoint, maximum flow occupies a sweet spot:

• It's powerful enough to model NP-complete problems in certain formulations
• Yet efficient polynomial-time algorithms exist for the standard version
• It provides a gateway to deeper optimization frameworks (linear programming, combinatorial optimization)

Algorithms like Ford-Fulkerson, Edmonds-Karp, and Dinic's algorithm solve maximum flow in polynomial time, making it practically applicable to real-world problem instances with millions of nodes and edges.

Before we can optimize flow, we need a precise way to measure it. The value of a flow quantifies the total amount of "stuff" moving from source to sink.

Definition — Value of Flow |f|:

The value of a flow f is the total flow leaving the source (equivalently, entering the sink):

$$|f| = \sum_{v \in V} f(s, v) - \sum_{v \in V} f(v, s) = \sum_{v \in V} f(v, t) - \sum_{v \in V} f(t, v)$$

In most formulations, we assume no edges enter the source and no edges leave the sink, simplifying to:

$$|f| = \sum_{v \in V} f(s, v) = \sum_{v \in V} f(v, t)$$

This equivalence follows from flow conservation: every unit of flow that leaves s must eventually reach t, since intermediate vertices neither create nor absorb flow.

Worked Example:

Consider this simple network with a valid flow (shown as flow/capacity):

         [A]
        ↗    ↘
    5/8      5/6
   ↗            ↘
[S]              [T]
   ↘            ↗
    3/5      3/4
        ↘    ↗
         [B]

Verification:

1. Capacity constraints: All flows (5, 5, 3, 3) are within edge capacities (8, 6, 5, 4). ✓

2. Conservation at A: Flow in = 5, Flow out = 5. ✓

3. Conservation at B: Flow in = 3, Flow out = 3. ✓

4. Value of flow: |f| = 5 + 3 = 8 (from source) = 5 + 3 = 8 (to sink). ✓

Is this maximum? Not necessarily! There might be unused capacity that could increase the flow. Finding the true maximum requires systematic exploration—which is exactly what flow algorithms provide.

A natural first instinct: find any path from s to t with available capacity, push as much flow as possible along it, repeat until no paths remain. This greedy approach seems reasonable but fails spectacularly in general.

The Classic Counterexample:

Consider this network:

      [A]
     ↗    ↘
   1       1
  ↗          ↘
[S]     1     [T]
  ↘          ↗
   1       1
     ↘    ↗
      [B]

With edge from A→B having capacity 1, and all other edges having capacity 1 as well.

Greedy Execution (Bad Luck):

Suppose greedy picks path S→A→B→T first and pushes 1 unit. Now:

• S→A is saturated (flow = capacity = 1)
• A→B is saturated (flow = capacity = 1)
• B→T is saturated (flow = capacity = 1)

Greedy concludes: Maximum flow = 1. No more paths exist.

But the actual maximum is 2:

• Path S→A→T carries 1 unit
• Path S→B→T carries 1 unit
• Total flow = 2

The Deep Insight:

The failure of greedy reveals a fundamental truth: we might need to "undo" previous decisions to find the global optimum.

This leads to the brilliant concept of residual graphs and augmenting paths:

• Instead of committing irrevocably to flow choices, we maintain the ability to "push flow back"
• The residual graph captures not just remaining forward capacity, but also the potential to redirect existing flow
• An augmenting path in the residual graph might use "backward edges" representing flow cancellation

This is the conceptual foundation of the Ford-Fulkerson method, which we'll explore in detail. The key insight: the ability to backtrack enables finding the true optimum, even when initial choices are suboptimal.

The residual graph is the conceptual breakthrough that makes efficient maximum flow algorithms possible. It elegantly encodes both unused forward capacity AND the potential to redirect existing flow.

Definition — Residual Graph G_f:

Given a flow network G = (V, E) with capacity function c and a flow f, the residual graph G_f = (V, E_f) is constructed as follows:

For each edge (u, v) ∈ E:

1. Forward edge: If f(u, v) < c(u, v), include edge (u, v) with residual capacity c_f(u, v) = c(u, v) - f(u, v). This represents remaining forward capacity.

2. Backward edge: If f(u, v) > 0, include edge (v, u) with residual capacity c_f(v, u) = f(u, v). This represents the ability to "cancel" existing flow.

The residual graph may have up to 2|E| edges: for each original edge, potentially one forward and one backward edge.

Worked Example:

Original network with current flow (flow/capacity):

[S] --5/10--> [A] --5/8--> [T]

Residual graph:

[S] --5--> [A] --3--> [T]     (forward edges: remaining capacity)
[S] <--5-- [A] <--5-- [T]     (backward edges: cancellation potential)

Reading the residual graph:

1. Forward S→A (capacity 5): We can push 5 more units from S to A
2. Backward A→S (capacity 5): We could cancel up to 5 units of S→A flow
3. Forward A→T (capacity 3): We can push 3 more units from A to T
4. Backward T→A (capacity 5): We could cancel up to 5 units of A→T flow

The augmenting path perspective:

An augmenting path is any path from s to t in the residual graph. The existence of an augmenting path means we can increase the total flow. The amount we can increase equals the minimum residual capacity along the path (the bottleneck).

The maximum flow problem has a fascinating history that intertwines with Cold War logistics, the birth of combinatorial optimization, and some of the most beautiful theorems in computer science.

Origins — The 1950s:

The formal study of network flows began in the 1950s, motivated by military logistics during the Cold War. The U.S. Air Force needed to understand the capacity of Soviet rail networks for transporting supplies. This practical problem led to foundational theoretical work.

Key Milestones:

1954 — Ford and Fulkerson: Lester Ford Jr. and Delbert Fulkerson, working at RAND Corporation, published the foundational paper establishing the Ford-Fulkerson method and proving the Max-Flow Min-Cut Theorem. This work is considered a cornerstone of combinatorial optimization.

1970 — Edmonds-Karp: Jack Edmonds and Richard Karp showed that using BFS to find augmenting paths guarantees O(VE²) time complexity, making the algorithm truly polynomial.

1970 — Dinic's Algorithm: Efim Dinic independently discovered a more efficient blocking flow approach achieving O(V²E) time, which was further improved for special cases.

Modern Developments: Advanced algorithms like Push-Relabel (Goldberg-Tarjan, 1988) and more recent near-linear time algorithms have continued to push the boundaries of efficiency.

We've established the foundations of the maximum flow problem. Let's consolidate what we've learned:

What's Next:

In the next page, we'll dive deeper into flow network components—examining sources, sinks, and capacities in detail. We'll explore how to properly model real-world problems as flow networks, including handling multiple sources/sinks, undirected edges, and vertex capacities. This modeling skill is often the difference between recognizing a flow problem and missing it entirely.