Advanced Network Flow

Overview

Network flow theory provides powerful tools for optimization on graphs. A flow network is a directed graph G = (V, E) with source s, sink t, and capacity function c: E -> R+. A flow assigns values to edges respecting capacity constraints and conservation at internal nodes.

Maximum Flow Problem

Find a flow from s to t that maximizes total flow value, subject to:

Capacity: 0 <= f(u,v) <= c(u,v) for all edges
Conservation: flow in = flow out at every vertex except s and t

Max-Flow Min-Cut Theorem (Ford-Fulkerson)

The maximum flow value equals the minimum capacity of an s-t cut.

An s-t cut (S, T) partitions V into S (containing s) and T (containing t). Cut capacity = sum of c(u,v) for edges from S to T.

Ford-Fulkerson Method

Augmenting Path Framework

Initialize f(e) = 0 for all edges
While there exists an augmenting path P in the residual graph G_f:
    delta = min residual capacity along P
    Augment flow along P by delta
Return f

Residual graph G_f: for each edge (u,v) with flow f(u,v) and capacity c(u,v):

Forward edge (u,v) with residual capacity c(u,v) - f(u,v) if positive
Backward edge (v,u) with residual capacity f(u,v) if positive
With integer capacities, terminates in O(|E| * max_flow) time
May not terminate with irrational capacities (pathological examples exist)

Edmonds-Karp Algorithm

Ford-Fulkerson with BFS to find shortest augmenting path (fewest edges).

While BFS finds augmenting path from s to t in G_f:
    delta = bottleneck capacity of path
    Update flow and residual graph

Analysis:

Each BFS takes O(E) time
Distance from s to any vertex in residual graph is non-decreasing
At most O(VE) augmentations
Total time: O(VE^2)

Dinic's Algorithm (Blocking Flow)

Uses level graph (BFS layers) and blocking flows for faster convergence.

While BFS from s reaches t in residual graph:
    Construct level graph L (edges only go to next BFS level)
    Find a blocking flow in L (saturates at least one edge on every s-t path)
    Add blocking flow to current flow

Blocking Flow via DFS

DFS(v, pushed):
    if v == t: return pushed
    while there is an edge (v, u) in level graph:
        d = DFS(u, min(pushed, residual(v, u)))
        if d > 0:
            update flow on (v, u) and (u, v)
            return d
        remove edge (v, u) from level graph  // dead end
    return 0

Analysis:

At most O(V) phases (distance to t increases each phase)
Each phase: O(VE) for blocking flow
Total: O(V^2 E)
Unit capacity graphs: O(E * sqrt(V)) — important for bipartite matching

Push-Relabel Algorithm (Goldberg-Tarjan)

Maintains a preflow (allows excess at vertices) instead of a valid flow.

Key Concepts

Height function h: V -> N with h(s) = |V|, h(t) = 0
Active vertex: has positive excess, is not s or t
Push: send flow from active vertex u to neighbor v if h(u) = h(v) + 1 and residual capacity > 0
Relabel: if active vertex u has no eligible neighbor, set h(u) = 1 + min h(v) over neighbors v with positive residual capacity

Generic Push-Relabel

Initialize: saturate all edges from s, set h(s) = |V|
While there exists an active vertex u:
    if u has an admissible edge (u,v): Push(u, v)
    else: Relabel(u)

Complexity

Generic: O(V^2 E)
FIFO selection: O(V^3) — process active vertices in FIFO order
Highest-label selection: O(V^2 sqrt(E)) — best strongly polynomial
Gap relabeling heuristic: significant practical speedup

Practical Advantages

Often faster than augmenting-path methods in practice
Naturally parallelizable (multiple pushes can occur simultaneously)
Works well with gap heuristic and global relabeling

Algorithm Comparison

| Algorithm | Time Complexity | Notes | |----------------|--------------------|--------------------------------| | Ford-Fulkerson | O(E * max_flow) | Integer capacities only | | Edmonds-Karp | O(VE^2) | Simple, BFS-based | | Dinic | O(V^2 E) | Best for unit-capacity graphs | | Push-Relabel | O(V^2 sqrt(E)) | Best for dense graphs | | Orlin | O(VE) | Theoretically optimal (2013) |

Minimum-Cost Flow

Find a flow of given value F at minimum total cost, where each edge has both a capacity and a per-unit cost.

Formulation

minimize    sum(cost(u,v) * f(u,v))
subject to  0 <= f(u,v) <= c(u,v)
            flow conservation at all internal vertices
            total flow from s to t = F

Successive Shortest Paths

Start with zero flow
Find shortest path (by cost) from s to t in residual graph
Augment along this path
Repeat until flow value = F

Requires no negative-cost cycles initially
Use Bellman-Ford or Johnson's algorithm for shortest paths
Time: O(F * V * E) with Bellman-Ford

Cycle-Canceling Algorithm

Find any max-flow (ignoring costs)
While there is a negative-cost cycle in the residual graph:
- Push flow around the cycle to reduce cost

Converges to optimal, but may be slow without careful cycle selection

Cost Scaling (Goldberg-Tarjan)

Epsilon-optimal flows: no negative cycle with cost < -epsilon * |V|
Scale epsilon from max_cost down to 1/|V|
Time: O(V^3 log(V * max_cost)) — strongly polynomial variant exists

Applications

Transportation and assignment problems
Optimal matching (min-weight perfect matching via reduction)
Circulation problems with lower bounds

Gomory-Hu Trees

A Gomory-Hu tree (cut tree) of an undirected graph G encodes the minimum s-t cut value for all pairs s, t in a single tree on V vertices.

Properties

Tree T on same vertex set V
Edge weight w(u,v) in T equals the min-cut value between u and v in G
The min-cut between any s, t in G equals the minimum weight edge on the s-t path in T
The partition given by removing this minimum edge from T gives the min-cut

Construction (Gusfield's Algorithm)

Initialize: tree T with all edges pointing to vertex 1
For i = 2 to n:
    Compute max-flow / min-cut between i and T-parent(i) in G
    Set weight of edge (i, parent(i)) in T to max-flow value
    For j > i: if T-parent(j) == T-parent(i) and j is on i's side of the cut:
        set T-parent(j) = i

Requires n - 1 max-flow computations
Total: O(V) max-flow calls, e.g., O(V * V^2 E) with Dinic's

Applications

All-pairs min-cut queries in O(V) time after O(V) preprocessing flows
Network reliability analysis
Image segmentation

Multi-Commodity Flow

Multiple commodities (source-sink pairs) share edge capacities.

Formulation

k commodities, each with source s_i, sink t_i, demand d_i
All commodities share edge capacities: sum of flows on each edge <= capacity
Feasibility: does a feasible multi-commodity flow exist?
Maximization: maximize total flow across all commodities

Complexity

Integer multi-commodity flow is NP-hard (even 2 commodities, unit capacities)
Fractional multi-commodity flow is solvable via LP
Approximate: multiplicative weights method gives (1+epsilon) approximation in O(epsilon^{-2} * E^2 * k) time [Garg-Konemann]

Max-Flow / Multi-Cut Duality

Multi-cut: remove minimum-weight edges to disconnect all (s_i, t_i) pairs
Fractional relaxation: max multi-flow <= min multi-cut
Integrality gap can be O(log k)

Network Design

Survivable Network Design

Design minimum-cost network satisfying connectivity requirements
r(u,v) = required edge-connectivity between u and v
2-approximation via iterative rounding of LP relaxation [Jain 2001]

Steiner Tree and Forest

Steiner tree: connect required terminals with minimum-cost tree
Best approximation: ln(4) + epsilon ~ 1.39 [Byrka et al.]
Steiner forest: connect specified pairs; 2-approximation via primal-dual

Applications

Bipartite matching: reduce to max-flow in O(E sqrt(V)) via Dinic's
Edge-disjoint paths: max number = max-flow (Menger's theorem)
Project selection: min-cut formulation for profit maximization with dependencies
Image segmentation: min-cut for foreground/background separation
Baseball elimination: flow network determines if team can still win
Airline scheduling: crew assignment, fleet routing

Summary

Network flow algorithms are among the most versatile tools in combinatorial optimization. The progression from Ford-Fulkerson to push-relabel represents both theoretical and practical advances. Extensions to min-cost flow, Gomory-Hu trees, and multi-commodity flow broaden applicability to logistics, scheduling, and network design problems.