5 min read
On this page

Network Flow

Network flow models the movement of quantities (data, goods, fluids) through a network. The max-flow problem and its dual (min-cut) connect to matching, scheduling, and many combinatorial optimization problems.

Definitions

Flow Network

A directed graph G = (V, E) with:

  • Source s: where flow originates
  • Sink t: where flow terminates
  • Capacity c(u, v) ≥ 0: maximum flow on edge (u, v)

Flow

A function f: E → ℝ satisfying:

  1. Capacity constraint: 0 ≤ f(u, v) ≤ c(u, v) for all edges
  2. Flow conservation: For all vertices except s and t: flow in = flow out

Flow value |f| = total flow out of s = total flow into t.

Residual Graph

Given a flow f, the residual graph Gf has:

  • Forward edges: (u, v) with residual capacity c(u, v) - f(u, v) (room to send more)
  • Backward edges: (v, u) with residual capacity f(u, v) (can cancel existing flow)

Augmenting Path

A path from s to t in the residual graph. Sending flow along this path increases the total flow.

Bottleneck: The minimum residual capacity along the path.

Max-Flow Min-Cut Theorem

Theorem (Ford-Fulkerson, 1956):

Maximum flow value = Minimum cut capacity

An s-t cut (S, T) partitions vertices into S (containing s) and T (containing t). Cut capacity = sum of capacities of edges from S to T.

Max-flow min-cut duality: The maximum amount of flow equals the minimum capacity that, if removed, disconnects s from t.

Algorithms

Ford-Fulkerson Method

Repeatedly find augmenting paths and send flow along them until no augmenting path exists.

1. Initialize f = 0 on all edges.
2. While there exists an augmenting path P in Gf:
   a. Compute bottleneck b = min residual capacity along P.
   b. Update flow: increase by b on forward edges, decrease by b on backward edges.
3. Return f.

Termination: With integer capacities, terminates in O(|f*| × E) time, where |f*| is the max-flow value. Can be exponentially slow with irrational capacities or poor path choices.

Edmonds-Karp Algorithm

Ford-Fulkerson with BFS (shortest augmenting path).

FUNCTION EDMONDS_KARP(cap, s, t)
    n ← number of vertices
    flow_total ← 0
    residual ← copy of cap

    LOOP
        // BFS to find augmenting path
        parent ← array of size n, all NIL
        visited ← array of size n, all false
        visited[s] ← true
        queue ← empty queue
        ENQUEUE(queue, s)

        WHILE queue is not empty
            u ← DEQUEUE(queue)
            FOR v ← 0 TO n - 1
                IF NOT visited[v] AND residual[u][v] > 0
                    visited[v] ← true
                    parent[v] ← u
                    ENQUEUE(queue, v)

        IF NOT visited[t] THEN BREAK   // no augmenting path

        // Find bottleneck
        bottleneck ← INFINITY
        v ← t
        WHILE parent[v] ≠ NIL
            u ← parent[v]
            bottleneck ← MIN(bottleneck, residual[u][v])
            v ← u

        // Update residual graph
        v ← t
        WHILE parent[v] ≠ NIL
            u ← parent[v]
            residual[u][v] ← residual[u][v] - bottleneck
            residual[v][u] ← residual[v][u] + bottleneck
            v ← u
        flow_total ← flow_total + bottleneck
    RETURN flow_total

Time: O(VE²). Each BFS finds a shortest augmenting path, and the shortest path length increases monotonically, so at most O(VE) augmentations.

Dinic's Algorithm

Uses blocking flows in the level graph (BFS layered graph).

  1. Build level graph using BFS from s.
  2. Find a blocking flow (a flow such that every s-t path in the level graph is saturated) using DFS.
  3. Add blocking flow to the total flow.
  4. Repeat from step 1.

Time: O(V²E). For unit-capacity graphs: O(E√V). For bipartite matching: O(E√V).

Much faster than Edmonds-Karp in practice. The standard choice for competitive programming.

Push-Relabel Algorithm

Instead of augmenting paths, works locally by pushing excess flow toward the sink.

Concepts:

  • Height function h(v): Labels vertices. Flow can only be pushed downhill (h(u) = h(v) + 1).
  • Excess e(v): Flow in - flow out at vertex v. Positive excess at non-source, non-sink vertices must be eliminated.
  • Push: Send excess from u to v (if h(u) = h(v) + 1 and residual capacity > 0).
  • Relabel: Increase h(v) if v has excess but can't push (no lower neighbor with residual capacity).

Time: O(V²E) generic. O(V³) with FIFO selection. O(V²√E) with highest-label selection.

Advantage: Better for dense graphs. No global augmenting path search — local operations.

Minimum Cost Flow

Find the maximum flow with minimum cost, where each edge has both a capacity and a cost per unit of flow.

Successive Shortest Paths

  1. Find the shortest path from s to t (minimum cost augmenting path) using Bellman-Ford or SPFA.
  2. Send flow along this path.
  3. Repeat until no more augmenting paths.

Time: O(VE × |f*|) or O(VE × F) where F is the max flow.

Cost-Scaling

A faster approach for minimum cost flow. O(V³ log V) time. The Goldberg-Tarjan algorithm.

Applications: Assignment problem, transportation problem, optimal matching.

Applications of Network Flow

Bipartite Matching via Flow

Model bipartite matching as a flow problem:

  • Source s connects to all vertices in U.
  • All vertices in V connect to sink t.
  • Edges from U to V with capacity 1.

Max-flow = maximum matching size.

Project Selection

Given projects with profits (positive) and costs (negative), and precedence constraints (project A requires project B):

Model as min-cut:

  • Source s represents "do the project."
  • Sink t represents "don't do the project."
  • Positive-profit projects: s → project with capacity = profit.
  • Negative-profit projects: project → t with capacity = |cost|.
  • Dependency A → B: B → A with infinite capacity.

Answer = total positive profits - min-cut value.

Image Segmentation

Segment an image into foreground and background:

  • Each pixel is a vertex.
  • Source s = foreground, sink t = background.
  • s → pixel: capacity = likelihood of foreground.
  • pixel → t: capacity = likelihood of background.
  • pixel → neighbor: capacity = smoothness penalty.

Min-cut gives the optimal segmentation.

Baseball Elimination

Determine if a team is mathematically eliminated from winning the division. Ford and Fulkerson showed this reduces to a max-flow problem.

Circulation with Demands

Flow conservation with demands: each edge has both a lower bound and upper bound on flow.

Feasibility: Reduce to standard max-flow by adding a super-source and super-sink.

Flow Decomposition

Any flow can be decomposed into at most E path flows and cycle flows.

Theorem: Any s-t flow f can be decomposed into at most E augmenting paths from s to t plus flow-carrying cycles.

This decomposition is useful for understanding the structure of flows and for practical routing.

Summary

| Algorithm | Time | Best For | |---|---|---| | Edmonds-Karp | O(VE²) | General, simple | | Dinic | O(V²E) | Competitive programming, unit-capacity | | Push-relabel (FIFO) | O(V³) | Dense graphs | | Push-relabel (highest) | O(V²√E) | Large sparse graphs | | Successive shortest paths | O(VE × F) | Min-cost flow |

Applications in CS

  • Network routing: Maximum data flow through a network. Bottleneck identification = min-cut.
  • Bipartite matching: Maximum matching in bipartite graphs (job assignment, course scheduling).
  • Image processing: Graph cuts for segmentation, stereo matching, denoising.
  • Airline scheduling: Crew scheduling, gate assignment, fleet routing.
  • Compiler optimization: Register allocation via network flow.
  • Supply chain: Transportation and transshipment problems.
  • Sports: Elimination problems in league standings.