1 Introduction to Network Flows
Network flows is a subfield of combinatorial optimization and applied mathematics concerned with the study of flow through a network, typically modeled as a directed or undirected graph with capacities on edges. The central problem involves determining the maximum amount of a commodity that can be sent from a source node to a sink node without violating capacity constraints, and includes related problems such as minimum-cost flow, multi-commodity flow, and flow with lower bounds. Network flow theory provides fundamental tools for modeling and solving a wide range of practical problems in logistics, telecommunications, supply chain management, and resource allocation, and is closely tied to graph theory, linear programming, and combinatorial algorithms.
1.1 Basic Definitions
1.1.1 Directed and Undirected Graphs
A network is represented as a graph \(G = (V, E)\), where \(V\) is the set of vertices (or nodes) and \(E\) the set of edges (or arcs). In a directed graph, each edge has an orientation from a tail to a head; in an undirected graph, edges have no orientation. Capacities are usually assigned to each edge, indicating the maximum amount of flow that can pass through it.
1.1.2 Source, Sink, and Internal Nodes
In flow problems, two special nodes are distinguished: the source \(s\) (where flow originates) and the sink \(t\) (where flow is collected). All other nodes are internal nodes, through which flow may pass or be conserved.
1.1.3 Capacity, Flow, and Conservation Constraints
Each edge \(e\) has a non-negative capacity \(c(e)\). A flow \(f\) assigns a value \(f(e)\) to each edge, satisfying \(0 \le f(e) \le c(e)\) (capacity constraints). At every internal node \(v\) (excluding source and sink), the net flow into \(v\) must equal the net flow out of \(v\) (flow conservation). The total flow value is the amount leaving the source (or arriving at the sink).
1.2 The Maximum Flow Problem
1.2.1 Formal Statement
Given a directed graph with capacities, source \(s\), and sink \(t\), the maximum flow problem asks for a flow \(f\) that maximizes the net flow out of \(s\) while respecting all capacity and conservation constraints. It is a linear programming problem with a simple combinatorial structure.
1.2.2 Feasible Flow and Saturated Edges
A flow satisfying all capacity and conservation constraints is called feasible. An edge is saturated if its flow equals its capacity. Saturated edges often form bottlenecks limiting further flow.
1.2.3 S-T Cuts and the Max-Flow Min-Cut Theorem
An \(s\)-\(t\) cut is a partition of \(V\) into two sets \(S\) and \(T\) with \(s \in S\), \(t \in T\). The capacity of the cut is the sum of capacities of edges from \(S\) to \(T\). The Max-Flow Min-Cut Theorem states that the maximum flow value equals the minimum capacity of any \(s\)-\(t\) cut. This fundamental duality result underpins many algorithms and applications.
1.3 Classification of Flow Problems
1.3.1 Single-Commodity vs. Multi-Commodity
Single-commodity flow deals with one type of commodity from one source to one sink. Multi-commodity flow involves several commodities, each with its own source-sink pair, sharing edge capacities. The latter is generally harder (NP-hard in the integral case).
1.3.2 Static vs. Dynamic (Time-Expanded) Flows
Static flows assume capacities are fixed over time. Dynamic flows incorporate time, often represented by time-expanded networks, allowing flow to traverse edges over multiple time steps. Problems include quickest transshipment and earliest arrival flows.
1.3.3 With or Without Edge Costs
In minimum-cost flow problems, each edge has a per-unit cost. The goal is to send a given amount of flow at minimum total cost. Without costs, the objective is simply to maximize flow value.
2 Classical Algorithms for Maximum Flow
2.1 Augmenting Path Algorithms
2.1.1 Ford-Fulkerson Method
2.1.1.1 Residual Graph and Augmenting Paths
The Ford-Fulkerson method iteratively finds a path from \(s\) to \(t\) in the residual graph—a graph where edges represent unused capacity and reverse edges represent flow that can be canceled. Each such augmenting path increases the flow by the minimum residual capacity along the path.
2.1.1.2 Complexity and Integer Capacity Assumption
If capacities are integers, the algorithm terminates after at most \(f^*\) augmentations, where \(f^*\) is the maximum flow value. With irrational capacities, it may not terminate or may converge to a non-optimal flow. For integer capacities, the running time is \(O(f^*E)\).
2.1.2 Edmonds-Karp Algorithm
2.1.2.1 Shortest Augmenting Path
The Edmonds-Karp algorithm is a refinement that selects the shortest augmenting path (in number of edges) in the residual graph using breadth-first search.
2.1.2.2 Running Time O(V E²)
By always choosing a shortest path, the number of augmentations is bounded by \(O(VE)\), leading to an overall \(O(VE^2)\) worst-case time. This improves on Ford-Fulkerson for large capacities.
2.2 Push-Relabel Algorithms
2.2.1 Preflow and Excess
Push-relabel algorithms maintain a preflow—a flow that may violate conservation by allowing excess at nodes. Each node has a height label. The algorithm pushes flow from higher to lower nodes and relabels nodes to create new opportunities.
2.2.2 Generic Push-Relabel Algorithm
The generic algorithm repeatedly selects an active node (with positive excess) and either pushes flow to a neighbor with lower height or relabels the node. It terminates when no active nodes remain, yielding a maximum flow.
2.2.3 Relabel-to-Front Variant
The relabel-to-front variant maintains a list of nodes and processes them in a fixed order, moving nodes to the front after relabeling. This gives an \(O(V^3)\) worst-case running time.
2.2.4 Global Relabeling Heuristics
Global relabeling periodically computes exact distances to the sink via BFS, resetting height labels. This improves practical performance by reducing unnecessary relabeling steps.
2.3 Dinic’s Algorithm and Scaling
2.3.1 Level Graphs and Blocking Flows
Dinic’s algorithm builds a level graph using BFS from \(s\), then repeatedly finds blocking flows (maximal flows that saturate at least one edge per path) using DFS. Each phase adds at least one unit of distance, giving \(O(V^2E)\) time.
2.3.2 Capacity Scaling Approach
Capacity scaling modifies the problem by considering only thresholds of capacity. It repeatedly doubles a scaling parameter, handling only edges with residual capacity above the threshold. This yields \(O(E \log C)\) augmentations for integer capacities, where \(C\) is the maximum capacity.
2.3.3 Comparison of Worst-Case Bounds
Dinic’s algorithm runs in \(O(V^2E)\); the push-relabel generic algorithm in \(O(V^3)\); and Edmonds-Karp in \(O(VE^2)\). For dense graphs, push-relabel is often faster; for sparse graphs, Dinic’s is competitive. Scaling approaches have polylogarithmic dependencies on capacities.
3 Minimum Cost Flow
3.1 Problem Formulation
3.1.1 Cost Coefficients and Supply-Demand Balance
Each edge has a cost \(w(e)\) per unit of flow. Nodes have supplies (positive) or demands (negative) whose sum is zero. The objective is to find a feasible flow (satisfying supplies/demands) that minimizes total cost while respecting capacities.
3.1.2 Optimality Conditions (Reduced Costs, Complementary Slackness)
A flow is optimal if there exists a set of node potentials such that reduced costs (cost minus potential difference) are non-negative on all edges (or zero on edges with flow). These conditions mirror linear programming duality and are used in algorithms.
3.2 Algorithms for Min-Cost Flow
3.2.1 Successive Shortest Path Algorithm
3.2.1.1 Potential Functions and Dijkstra’s Algorithm
Starting with zero flow, the algorithm repeatedly finds shortest paths (by reduced cost) in the residual graph using Dijkstra’s algorithm (with non-negative reduced costs maintained via potentials). Each path augments flow and updates potentials.
3.2.1.2 Scaling for Negative Cycles
If negative cycles exist initially, a preprocessing scaling step can eliminate them by first adding a large supply/demand and canceling cycles. Alternatively, successive shortest path works only with non-negative costs; otherwise Bellman-Ford is used initially.
3.2.2 Cycle-Canceling Algorithm
The cycle-canceling algorithm starts with any feasible flow, then repeatedly finds negative-cost cycles in the residual graph and sends flow around them to reduce cost. The number of iterations depends on cost and capacity bounds.
3.2.3 Network Simplex Method
The network simplex method adapts the simplex algorithm of linear programming to network flow, maintaining a spanning tree basis. It is highly efficient in practice, especially for large sparse networks, and is the standard for solving min-cost flow problems in commercial solvers.
3.3 Applications
3.3.1 Transportation and Assignment Problems
The transportation problem (min-cost movement of goods from suppliers to consumers) and the assignment problem (min-cost matching of workers to jobs) are classic special cases of min-cost flow. They can be solved efficiently using network flow algorithms.
3.3.2 Minimum Cost Circulation
A circulation is a flow where every node has net supply zero. Finding a circulation of minimum cost is a fundamental problem with applications in balancing transactions, traffic assignment, and economic equilibrium.
4 Advanced Topics and Extensions
4.1 Multi-Commodity Flows
4.1.1 Fractional vs. Integral Flows
In multi-commodity flow, the fractional version (allowable split) is solvable in polynomial time via linear programming. The integral version (each commodity must send an integer amount) is NP-hard in general, unless the graph is series-parallel or the number of commodities is fixed.
4.1.2 Approximation Algorithms and LP-Based Approaches
Since multi-commodity flow is computationally hard, approximation algorithms exist, often based on linear programming relaxations, randomized rounding, or the multiplicative weight update method. The classical result is the \(O(\log n)\)-approximation for maximum concurrent flow.
4.2 Flow with Lower Bounds and Circulation
4.2.1 Feasibility Conditions (Cut Criterion)
For a circulation with lower bounds \(\ell(e)\) and upper bounds \(u(e)\), feasibility requires that for every cut, the sum of lower bounds from \(S\) to \(T\) does not exceed the sum of upper bounds from \(S\) to \(T\). This generalizes the cut condition for maximum flow.
4.2.2 Transformation to Standard Form
Lower bounds can be eliminated by setting capacity to \(u(e)-\ell(e)\) and adjusting node supplies: the node at the tail gains \(\ell(e)\) supply, the head loses \(\ell(e)\). The resulting problem has no lower bounds and can be solved by standard max-flow or min-cost flow algorithms.
4.3 Dynamic and Time-Dependent Flows
4.3.1 Discrete-Time Models
In discrete-time dynamic flows, time is divided into integer time steps. Each edge has a transit time and capacity per time unit. The time-expanded network replicates the graph for each time step, enabling static flow algorithms on an expanded graph.
4.3.2 Earliest Arrival and Quickest Transshipment
The earliest arrival flow sends flow so that the amount arriving at the sink by any time \(T\) is maximal. The quickest transshipment problem finds the minimum time to send a given amount of flow. These problems are solved using min-cost flow or max flow on time-expanded networks.
4.4 Network Flow in Bipartite Matching
4.4.1 Reduction to Maximum Flow
A bipartite graph can be transformed into a flow network by adding a source connected to one partition, sink to the other, and setting all capacities to 1. The maximum flow corresponds to a maximum cardinality matching.
4.4.2 Hall’s Marriage Theorem and Applications
Hall’s theorem (a perfect matching exists iff every subset of one partition has at least as many neighbors in the other) is a direct consequence of the max-flow min-cut theorem. Applications include job assignment, room scheduling, and stable marriage problems.
4.5 Connections to Linear Programming and Duality
4.5.1 LP Formulation of Max Flow and Min Cut
The maximum flow problem can be written as a linear program, with variable \(f(e)\) and constraints. The dual of this LP is the minimum cut problem, providing an alternative interpretation via edge cut capacities. This duality extends to minimum cost flow.
4.5.2 Dual Interpretation and Pathologies
The dual variables for conservation constraints are node potentials; for capacity constraints, they correspond to multipliers on edges. In the presence of degeneracy or scaling issues, interpretation can be subtle, but duality remains a cornerstone of network flow theory.
5 Applications of Network Flows
5.1 Transportation and Logistics
5.1.1 Vehicle Routing and Fleet Assignment
Network flow models help assign vehicles to routes or deliveries, minimizing distance or cost subject to capacity and time constraints. Maximum flow can check feasibility; min-cost flow optimizes routing.
5.1.2 Supply Chain Network Design
Supply chain networks—factories, warehouses, retailers—are modeled as flows with multiple layers. Min-cost flow determines optimal production levels and shipping quantities, while multi-commodity flow handles multiple products.
5.2 Telecommunications and Data Networks
5.2.1 Routing and Bandwidth Allocation
Data packets are routed through a network of routers and links with bandwidth capacities. Maximum flow identifies bottlenecks; min-cost flow finds cheapest routing. Traffic engineering uses multi-commodity flow for load balancing.
5.2.2 Survivable Network Design
Survivable network design aims to ensure connectivity after failures. Network flow formulations help compute minimum-cost capacity augmentation to guarantee a certain flow level even after edge failures, often using cut-based constraints.
5.3 Image Processing and Computer Vision
5.3.1 Graph Cuts for Segmentation
In image segmentation, each pixel is a node, and edges encode similarity. A min-cut (or max-flow) partition separates foreground from background, minimizing an energy function. This technique is widely used in interactive segmentation and 3D modeling.
5.3.2 Energy Minimization via Min-Cut
Many computer vision problems (stereo vision, image restoration) are formulated as energy minimization with submodular pairwise terms, which can be solved exactly by computing a minimum cut in a specially constructed graph.
5.4 Scheduling and Resource Allocation
5.4.1 Project Scheduling with Resource Constraints
Projects with tasks that consume limited resources can be modeled as a flow network. Min-cost flow determines the optimal allocation of resources to tasks over time, respecting precedence and capacity.
5.4.2 Job Assignment and Load Balancing
Assigning jobs to machines to minimize cost or maximize throughput is a classic transportation problem. Load balancing in distributed systems uses max-flow to check feasibility of task assignment under resource limits.