Network flow problem

In combinatorial optimization, network flow problems are a class of computational problems in which the input is a flow network (a graph with numerical capacities on its edges), and the goal is to construct a flow, numerical values on each edge that respect the capacity constraints and that have incoming flow equal to outgoing flow at all vertices except for certain designated terminals.^[1]

Specific types of network flow problems include:

• The maximum flow problem, in which the goal is to maximize the total amount of flow out of the source terminals and into the sink terminals^{[1]: 166–206}
• The minimum-cost flow problem, in which the edges have costs as well as capacities and the goal is to achieve a given amount of flow (or a maximum flow) that has the minimum possible cost^{[1]: 294–356}
• The multi-commodity flow problem, in which one must construct multiple flows for different commodities whose total flow amounts together respect the capacities^{[1]: 649–694}
• Nowhere-zero flow, a type of flow studied in combinatorics in which the flow amounts are restricted to a finite set of nonzero values

The max-flow min-cut theorem equates the value of a maximum flow to the value of a minimum cut, a partition of the vertices of the flow network that minimizes the total capacity of edges crossing from one side of the partition to the other. Approximate max-flow min-cut theorems provide an extension of this result to multi-commodity flow problems. The Gomory–Hu tree of an undirected flow network provides a concise representation of all minimum cuts between different pairs of terminal vertices.

Algorithms for constructing flows include

• Dinic's algorithm, a strongly polynomial algorithm for maximum flow^{[1]: 221–223}
• The Edmonds–Karp algorithm, a faster strongly polynomial algorithm for maximum flow
• The Ford–Fulkerson algorithm, a greedy algorithm for maximum flow that is not in general strongly polynomial
• The network simplex algorithm, a method based on linear programming but specialized for network flow^{[1]: 402–460}
• The out-of-kilter algorithm for minimum-cost flow^{[1]: 326–331}
• The push–relabel maximum flow algorithm, one of the most efficient known techniques for maximum flow

Otherwise the problem can be formulated as a more conventional linear program or similar and solved using a general purpose optimization solver.

Network flow problems have diverse applications across computer science, materials science, geophysics, and sports management.

In sports analytics, maximum flow algorithms are used to solve the baseball elimination problem, first formulated by Schwartz in 1966. The problem determines whether a team in a sports league is mathematically eliminated from winning their division based on current standings and remaining matchups. This is modeled as a network flow where game matchups represent sources of flow, and teams represent sinks; if the maximum flow does not fully saturate the edges leaving the game nodes, the team is eliminated.^[2] Kevin D. Wayne expanded on this by proving a "threshold property" of the standings, showing that the parametric maximum flow algorithm can identify all eliminated teams in a league in the same asymptotic time complexity as finding a single maximum flow.^[3]

In materials science and computational solid mechanics, the path of a crack or rupture propagating through a heterogeneous material can be modeled using the duality between continuous maximum flow and minimum cuts. Building on the continuous max-flow/min-cut theorem established by mathematician Gilbert Strang in 1983,^[4] the "path of least resistance" for a crack corresponds to a continuous minimum cut across the domain, where local material fracture toughness is represented as a spatially varying capacity. By solving the dual continuous maximum flow problem on a combinatorially consistent grid (such as using Fast Fourier Transform and Alternating Direction Method of Multipliers algorithms), researchers can compute the effective macroscopic crack energy and exact fracture paths without suffering from grid-orientation bias.^[5]

In geophysics, network flow optimization is used to map 3D earthquake fault rupture geometries using satellite-based Interferometric Synthetic Aperture Radar (InSAR). Because InSAR phase data is wrapped within cyclic intervals of $[-\pi, \pi]$, converting it into continuous ground displacement requires phase unwrapping. The standard tool for this task, the Statistical-Cost, Network-Flow Algorithm for Phase Unwrapping (SNAPHU), formulates 2D phase unwrapping as a minimum-cost network flow problem on a grid.^[6] The resulting continuous deformation maps are then inverted using elastic dislocation models to reconstruct the fault slip distribution and active rupture geometry.

Index of articles associated with the same name

This set index article includes a list of related items that share the same name (or similar names).
If an internal link incorrectly led you here, you may wish to change the link to point directly to the intended article.