Network Flow Algorithms
Network flow algorithms compute the maximum amount of flow that can be sent from a source to a sink through a capacitated network, a problem whose optimum is tied by duality to the network's minimum cut.
Definition
A flow network is a directed graph with edge capacities, a source, and a sink; a maximum-flow algorithm finds an assignment of flow to edges, respecting capacities and conservation at intermediate vertices, that maximizes the total flow from source to sink.
Scope
This topic covers the maximum-flow problem and its algorithms: the Ford-Fulkerson method with augmenting paths, the Edmonds-Karp and Dinic refinements that bound running time, and the max-flow min-cut theorem that characterizes the optimum. It also covers reductions of other problems — bipartite matching, vertex-disjoint paths, project selection — to network flow. It excludes general linear programming, of which flow is a special case.
Core questions
- How is a flow defined, and what constraints must it satisfy?
- How do augmenting paths in the residual graph increase flow toward the maximum?
- Why does the maximum flow equal the minimum cut capacity?
- How do Edmonds-Karp and Dinic's algorithm guarantee polynomial running time?
- How are matching and other problems reduced to maximum flow?
Key concepts
- flow network
- capacity and conservation
- augmenting path
- residual graph
- max-flow min-cut theorem
- Edmonds-Karp algorithm
- Dinic's algorithm
- bipartite matching reduction
Key theories
- Max-flow min-cut theorem
- The value of a maximum flow from source to sink equals the minimum capacity of a cut separating them; this duality, due to Ford and Fulkerson, certifies optimality and links flow to connectivity and partitioning problems.
- Augmenting paths and residual graphs
- The Ford-Fulkerson method increases flow by finding paths with spare capacity in the residual graph; choosing shortest augmenting paths (Edmonds-Karp) or using level graphs and blocking flows (Dinic) yields polynomial-time guarantees.
Clinical relevance
Network flow is a versatile modeling tool: it solves bipartite assignment and scheduling, computes connectivity and reliability of networks, performs image segmentation via graph cuts in computer vision, and underpins logistics, transportation planning, and project-selection optimization where capacities and bottlenecks matter.
History
Ford and Fulkerson introduced the maximum-flow problem and the max-flow min-cut theorem in 1956 while studying transportation networks. Edmonds and Karp (1972) and, independently, Dinic (1970) gave the first polynomial-time algorithms, and subsequent work has steadily improved the asymptotic running time of maximum flow.
Key figures
- Lester Ford
- Delbert Fulkerson
- Jack Edmonds
- Yefim Dinic
Related topics
Seminal works
- fordfulkerson1956
- cormen2009
Frequently asked questions
- What does the max-flow min-cut theorem actually say?
- It states that the largest amount of flow you can push from source to sink equals the smallest total capacity of any set of edges whose removal disconnects the source from the sink. The minimum cut acts as the bottleneck that limits the maximum flow.
- Why does plain Ford-Fulkerson not have a polynomial running time?
- If augmenting paths are chosen poorly and capacities are large (or irrational), the number of augmentations can be huge or even fail to terminate. Choosing shortest augmenting paths (Edmonds-Karp) or using blocking flows (Dinic) bounds the number of augmentations and gives polynomial time.