Why Capacity Matters to Ford–Fulkerson
Ford–Fulkerson repeatedly searches for a source-to-sink path in the residual network and sends as much additional flow as that path permits. With integer capacities, each successful update increases the flow value by at least one. This gives a useful bound in terms of the maximum flow value \(F\), but \(F\) can be exponentially large compared with the number of bits used to write the capacities.
Throughout, a network is a finite directed graph \(G=(V,E)\) with distinct source \(s\) and sink \(t\), and a nonnegative capacity \(c(e)\) on each arc \(e\). Write \(n=|V|\) and \(m=|E|\). Capacities in the main bound are integers. The algorithm starts with the zero flow. A residual arc records how much flow can still be sent forward, or how much existing flow can be cancelled in the reverse direction. For each original arc, a residual representation needs at most two arc records, so it has \(O(m)\) arcs.
A path search implemented with adjacency lists takes \(O(n+m)\) time: it marks or initializes vertices, and examines each vertex and residual arc at most a constant number of times. Updating the flow along a simple path also takes \(O(n)\) time, since a simple path has at most \(n-1\) arcs. These costs are included in \(O(n+m)\). The analysis counts graph operations with unit-cost capacity arithmetic; the implications of binary arithmetic are discussed below.
Bounding the Number of Augmentations
Proof. Initially the flow value is \(0\), an integer. When the current flow has integer values on all arcs, every residual capacity is an integer: forward residual capacities are capacity minus flow, and reverse residual capacities equal flow. Thus the bottleneck \(\Delta\), being the minimum of the positive integer residual capacities on the chosen path, is an integer with \(\Delta\ge1\). The update preserves integer flow values and increases the flow value by exactly \(\Delta\). After \(q\) augmentations the flow value is therefore an integer at least \(q\). Each intermediate flow is feasible, so its value cannot exceed the maximum value \(F\); hence \(q\le F\). In particular there can be at most \(F\) augmentations, and the algorithm cannot continue augmenting indefinitely. It stops when a search finds no residual source-to-sink path. By the augmenting-path characterization of maximum flows, the flow at that point is maximum. \(\square\)
The integer hypothesis matters: it supplies a positive lower bound of \(1\) on every augmentation. The proof does not say that every augmentation has size \(1\), nor that the algorithm makes exactly \(F\) augmentations. A large bottleneck can send several units at once.
Worked Example: Three Augmentations and a Final Search
Let \(V=\{s,a,b,t\}\), with directed arcs and capacities \(s\to a:3\), \(a\to t:2\), \(s\to b:2\), \(b\to t:3\), and \(a\to b:1\). The algorithm uses the following valid residual paths.
| Search | Residual path returned (or reachable vertices) | Bottleneck or outcome | Flow value after search |
|---|---|---|---|
| 1 | \(s\to a\to t\) | \(\min(3,2)=2\); augment by \(2\) | \(2\) |
| 2 | \(s\to b\to t\) | \(\min(2,3)=2\); augment by \(2\) | \(4\) |
| 3 | \(s\to a\to b\to t\) | \(\min(1,1,1)=1\); augment by \(1\) | \(5\) |
| 4 | Reachable from \(s\): \(\{s\}\) | \(t\) is not reachable; no augmentation | \(5\) |
After the first augmentation, the flows on \(s\to a\) and \(a\to t\) are \(2\) each. After the second, the flows on \(s\to b\) and \(b\to t\) are \(2\) each. Before the third search, the remaining forward residual capacities on \(s\to a\), \(a\to b\), and \(b\to t\) are \(3-2=1\), \(1-0=1\), and \(3-2=1\), respectively. The third augmentation therefore adds \(1\) on each of those arcs.
Check: The final flow has value \(5\). The total capacity of the arcs entering \(t\) is \(2+3=5\), so no flow can have value greater than \(5\). The exhibited feasible flow has value \(5\), proving \(F=5\). There were \(3\le5\) successful augmentations, followed by a fourth, unsuccessful search.
Counting Searches, Including the Last One
The augmentation theorem bounds successful searches, but the algorithm must also determine that no augmenting path remains. Therefore, if \(F\ge0\), there are at most \(F+1\) path searches in total: at most \(F\) that find a path, and one final search that does not. Each search and its associated update cost \(O(n+m)\). Consequently the general bound is
When \(F\ge1\), \(F+1\le2F\), so this is \(O((n+m)F)\). If the network has no isolated vertices, then \(n\le2m\), because each vertex is incident with at least one of the \(m\) arcs and the arcs have two endpoints. In that case \(n+m=O(m)\), giving the often-quoted \(O(mF)\) bound for \(F\ge1\). If isolated vertices are allowed, retaining \(n+m\) avoids silently assuming that \(n=O(m)\).
Worked Example: Zero Maximum Flow Still Requires a Search
Let \(V=\{s,a,b,t\}\), and let the directed arcs be \(s\to a\) and \(a\to b\), each of capacity \(7\). There are no other arcs. Since \(t\) has no incident arcs, no positive flow can reach it, and \(F=0\).
| Search stage | Vertices reached from \(s\) | Tree arcs examined or retained | Result |
|---|---|---|---|
| Start at \(s\) | \(\{s\}\) | \(s\to a\), residual capacity \(7\) | Discover \(a\) |
| Continue from \(a\) | \(\{s,a\}\) | \(a\to b\), residual capacity \(7\) | Discover \(b\) |
| Continue from \(b\) | \(\{s,a,b\}\) | No outgoing residual arc leads to \(t\) | Search ends unsuccessfully |
The search examines the two arcs and establishes that \(t\) is unreachable; there is no successful augmentation. Its work is \(O(n+m)\), which here is \(O(4+2)\), not zero.
Check: Substituting \(F=0\) into the corrected bound gives \(O((n+m)(0+1))=O(n+m)\). By contrast, the expression \(O((n+m)F)\) would evaluate to zero and cannot account for the required unsuccessful search.
Why the Bound Is Not Polynomial in Binary Input Length
In the usual input representation, a capacity is written in binary. A capacity of \(2^k\) takes \(k+1\) bits: its binary representation is a \(1\) followed by \(k\) zeroes. Thus a numerical value can be exponentially larger than the number of bits used to encode it. Since the Ford–Fulkerson bound depends on the numerical value \(F\), it is not, by itself, a polynomial bound in the binary input length.
Worked Example: A Large Flow Value in a Short Encoding
For each positive integer \(k\), take \(V=\{s,t\}\) with the single directed arc \(s\to t\) of capacity \(2^k\). The maximum flow value is \(F=2^k\), since that arc can carry at most its capacity and can carry that amount. Starting from zero, Ford–Fulkerson finds the one-arc path \(s\to t\), whose bottleneck is \(2^k\), and sends \(2^k\) units in one augmentation. The next search fails.
For the particular value \(k=10\), the capacity is \(2^{10}=1024\), whose binary representation is \(10000000000\), with \(11\) bits. The capacity-dependent expression \(mF\) is \(1\cdot1024=1024\), while the capacity uses \(11\) bits.
Check: For general \(k\), the graph structure is fixed, the capacity encoding uses \(k+1\) bits, and the parameter in the bound is \(F=2^k\). The function \(2^k\) is not bounded by any polynomial in \(k\). This shows that the bound \(O(mF)\) does not provide a polynomial-time guarantee in binary input length. It does not show that this particular one-arc instance takes exponentially many operations: the calculation above shows it finishes after one augmentation.
Common Pitfall: Dropping the Terminal Search
A frequent incorrect count is: “There are at most \(F\) augmentations, each costing \(O(n+m)\), so the whole algorithm costs \(O((n+m)F)\).” The calculation counts only searches that find paths. It omits the search that returns “no path,” which is necessary to know that the algorithm has finished. When \(F=0\), this omission is especially visible: the incorrect expression predicts zero work, although a search may still scan a large reachable part of the network.
The safe count is always “successful searches plus one terminal search,” giving \(F+1\). For \(F\ge1\), replacing \(F+1\) by \(O(F)\) is valid. For \(F=0\), use the separate \(O(n+m)\) search bound. Also keep the augmentation count distinct from the running time: even a valid count of \(F\) augmentations must still be multiplied by the work per search and update.
Check Your Understanding
Use the integer-capacity augmentation argument and count the terminal search explicitly.
- Why must every successful augmentation have size at least \(1\) when all capacities are integers?
- If \(F=6\), what is the maximum number of successful augmentations, and how many searches should be included in the total bound?
- Explain why \(O((n+m)F)\) cannot be the complete search bound when \(F=0\).
- A single arc has capacity \(2^k\). How many bits are needed to encode this capacity in binary, and what is the maximum flow value?
- Why does a bound expressed in terms of \(F\) fail to certify polynomial running time in binary input length, even though a particular network with large \(F\) might be solved quickly?