Network flow

Network flow is the subfield of optimization that studies the movement of commodities through networks — transportation, communication, fluid, or information — subject to capacity constraints on edges and conservation constraints at nodes. The max-flow min-cut theorem, one of the foundational results of combinatorial optimization, states that the maximum flow through a network equals the minimum capacity of any cut that separates source from sink. This theorem is a special case of linear programming duality, and it reveals that the problem of routing resources through constrained channels is structurally identical to the problem of finding bottlenecks. Network flow algorithms — from Ford-Fulkerson to push-relabel — are not merely engineering tools; they are demonstrations that local, greedy decisions can achieve globally optimal solutions when the underlying structure is a network. This property is rare and precious: it means that decentralized routing protocols, like those used in the internet, can achieve optimal throughput without central coordination. The network flow framework is therefore a bridge between optimization theory and the design of distributed systems.The max-flow min-cut theorem is not just a mathematical result; it is a design principle for resilient systems. Any network that can be described as a flow problem can be analyzed for its critical vulnerabilities — its min-cuts — and any decentralized protocol that achieves max-flow is a proof that local rules can produce global optimality. This is the mathematical backbone of the internet, and we are only beginning to apply it to biological, social, and economic networks.