Summary
Maximum flow problem on directed graphs: find the most flow from source to sink respecting edge capacities. Connects to minimum cuts via the max-flow min-cut theorem ( for the optimal s-t cut).
We are dealing with directed graphs with a source vertex and a sink vertex . Each edge has a capacity , and we define if . When drawing a graph, we write on an edge to mean “currently flowing 2 out of a max capacity of 3.” The goal is to push as much flow as possible from to .
Net Flow
A net flow is a function that assigns a real number to every pair of vertices. This value can be negative: if , it means there is flow of going from to instead.
The value of a flow is (the total flow leaving the source).
Flow Constraints
Every valid flow must satisfy three rules:
- Feasibility: (you can’t exceed the capacity of an edge)
- Conservation: (at every vertex except and , flow in equals flow out)
- Skew symmetry: (flow from to is the negative of flow from to )
Lemma (Flow Decomposition)
Let be the subgraph of containing only edges where . This support graph can be decomposed into a collection of - flow paths and flow cycles.
Checking
To check whether the max flow is positive, just check if there exists any - path in (ignoring zero-capacity edges). If such a path exists, .
Let (the set of vertices reachable from ). We know , and if then (the sink is unreachable).
s-t Cut
An s-t cut is a partition of the vertices into two sets such that and .
The capacity of a cut is the total capacity of edges crossing from to :
Only edges going from to count, not edges going back.
Key Equivalence
Minimum s-t Cut Problem
We want to find an s-t cut in with minimum capacity. The net flow across a cut is:
This sums all the positive flow leaving and subtracts everything flowing back into . By feasibility, (the net flow across any cut can’t exceed the cut’s capacity).
Claim: Flow Across Any Cut Equals
For any two s-t cuts and , we have . The intuition is:
- A cycle staying entirely within one side of the cut contributes nothing (it never crosses).
- A cycle crossing the cut has net contribution 0 (it leaves and comes back).
- An - path crosses the cut exactly once more in the forward direction than backward.
Since (the flow value is the net flow out of alone), this means for any s-t cut .
Weak Duality
For any flow and any s-t cut :
In particular, for every s-t cut. The maximum flow value can never exceed the capacity of any cut.
Max Flow Problem
A naive approach is to start with zero flow, find an - path with positive capacity, and push flow along it. That sounds reasonable, but it can get stuck because an early choice may block a better routing later. The fix is to let ourselves undo earlier choices when needed, which is exactly what residual networks do.
If you want one sentence to remember: max flow is not just “keep adding flow,” it is “keep adding flow while preserving the option to reroute it later.”
Residual Networks
Residual Network
Given a flow in , the residual network has residual capacities:
This tells us how much additional flow we can push along each edge. An edge if and only if .
Why Reverse Edges Appear
Residual networks automatically include reverse edges that let us “undo” flow. If we’re currently sending flow from to , then by skew symmetry , so:
This means even if there was no original edge from to . Pushing flow along this reverse edge effectively cancels some of the flow we previously sent from to .
By feasibility, residual capacities satisfy .
Lemma (Flow Composition)
If is a valid flow in and is a valid flow in , then is a valid flow in with value .
Augmenting Paths
To improve a flow , find an - path in the residual network . This is called an augmenting path. Push flow along up to its bottleneck (the smallest residual capacity along the path):
Ford-Fulkerson Algorithm
Ford-Fulkerson
- Start with zero flow .
- Build the residual network .
- Find an augmenting path in .
- Push units of flow along (updating ).
- Repeat from step 2 until no augmenting path exists.
Each iteration takes time (finding a path and updating). The number of augmentations is at most where , giving total runtime . This is pseudopolynomial: polynomial in the value of , not in the number of bits needed to represent .
Strong Duality (Max-Flow Min-Cut Theorem)
When Ford-Fulkerson terminates (no augmenting paths remain), the flow is optimal. Here is why:
If there are no augmenting paths, there is no - path in . Define . Since , this is a valid s-t cut. For every edge crossing the cut, for , meaning . Expanding:
Setting gives . Combined with weak duality:
The maximum flow value equals the minimum cut capacity.
Theorem (Max-Flow Min-Cut)
The following are equivalent:
- for some s-t cut .
- is a maximum flow.
- admits no augmenting path in .
Theorem (Flow Integrality)
If all capacities are integers, then is an integer and there exists a max flow where every edge carries integer flow. Ford-Fulkerson will find such a flow.
There are cases where Ford-Fulkerson can take a very long time, namely when capacities are large relative to the graph size. The pseudopolynomial runtime means it’s fine for small-capacity networks but can be exponentially slow when is encoded in binary (e.g., ).
Maximum Bottleneck Path Algorithm (MBP)
Instead of picking any augmenting path, we choose the path in each iteration that maximizes the residual bottleneck capacity . This path can be found in time.
Claim
In any graph , there exists an - path with
To see why: by the flow decomposition lemma, the max flow decomposes into at most flow paths and cycles. The entire value is carried by at most paths. By averaging, at least one path must carry flow, so its bottleneck capacity is at least .
MBP Runtime:
Let be the remaining “missing” flow at the start of iteration (i.e., where is the flow pushed so far). By our claim applied to the residual network, the bottleneck path pushes at least flow, so:
After iterations: . By the integrality theorem, if then , so the algorithm terminates.
Each iteration costs , and we need at most iterations, giving total. This is a weakly polynomial runtime (the dependence on the input numbers is only logarithmic).
Using BFS to find the shortest augmenting path gives the Edmonds-Karp algorithm with runtime . The analysis is more involved, but the key idea is that shortest-path distances in can only increase over time, bounding the total number of augmentations to .
Bipartite Matching
A bipartite graph has two disjoint sets of vertices and , where every edge goes between and (no edges within the same side). A matching is a subset of edges where no vertex appears more than once, i.e., every vertex is “used” at most once. The goal is to find a matching with the most edges possible (maximum cardinality). This is one of the most important applications of max flow: many assignment and scheduling problems reduce to bipartite matching.
A classic example: is a set of jobs and is a set of machines, with an edge meaning machine can handle job . We want to assign as many jobs as possible, but each machine can only do one job and each job only needs one machine.
Reduction to Max Flow
This problem reduces to maximum flow. Given a bipartite graph :
- Direct all edges from to , each with capacity 1.
- Add a source with a capacity-1 edge to every vertex in .
- Add a sink with a capacity-1 edge from every vertex in to .
Since all capacities are 1, the integrality theorem guarantees the max flow is integer-valued, meaning each edge either carries flow 0 or 1. The capacity-1 edges from ensure each vertex in sends flow to at most one neighbor, and the capacity-1 edges to ensure each vertex in receives from at most one neighbor. So any integer max flow corresponds to a valid matching, and vice versa.
Claim
The max flow value equals the size of the maximum matching: .
Proof
We show both directions.
Matching flow (): Given any matching , build a flow by sending 1 unit along for each matched edge . This is a valid flow: every edge carries flow 0 or 1 (feasibility), and each vertex in and is in at most one matched edge (conservation). The flow value is , so . Since this holds for every matching, .
Flow matching (): Take the integer max flow (exists by the integrality theorem). Every edge carries flow 0 or 1. Define . This is a valid matching: each has at most 1 unit entering from (capacity 1), so at most one edge from carries flow, meaning appears in at most one matched edge. Similarly, each has at most 1 unit leaving to , so appears at most once. The matching size is , so .
Combining both: , so .
Ford-Fulkerson on this network runs in time: each augmentation takes and pushes 1 unit of flow (since all capacities are 1), so there are at most augmentations.