From an Augmentation Bound to a Running-Time Bound
Edmonds–Karp is the Ford–Fulkerson method in which each augmenting path is chosen by breadth-first search (BFS), so it has the fewest arcs among the available residual paths. Its total running time depends on two separate counts: how many augmentations occur, and how much work one search and residual update require. The earlier material on the Edmonds–Karp \(O(VE)\) augmentation bound gives the first count. Here we account for the work per augmentation and combine the two.
Throughout, a network is a finite directed graph with source \(s\), sink \(t\ne s\), and a nonnegative capacity on each original arc. Write \(n=|V|\) and \(m=|E|\), where \(E\) is the set of original arcs. Assume adjacency-list storage and constant-time arithmetic and comparison of capacities. Complexity is measured in these operations; bit complexity for encoding large capacities is not included.
For implementation, each original arc can be stored with its paired reverse residual arc. This gives at most \(2m\) stored residual arcs. If an input has arcs in both directions between a pair of vertices, each original arc still has its own paired reverse entry. This representation avoids ambiguity about which flow an update changes.
The Work in One Search and Update
BFS starts at \(s\) and scans the residual adjacency list of each vertex it reaches. It records predecessors so that, if \(t\) is reached, the path can be recovered by following predecessor pointers backwards. Each reached vertex is enqueued at most once, and each stored residual arc is examined at most once in that search. A search therefore costs \(O(n+m)\) if it initializes or clears labels for all vertices.
For the sharper per-search \(O(m)\) bound, ignore isolated vertices other than \(s,t\), since no residual path can use them. This deletion is a one-time preprocessing step costing \(O(n+m)\). In the remaining graph, every vertex other than possibly \(s,t\) is incident with an original arc, so there are at most \(2m+2\) vertices. For \(m\ge1\), BFS visits at most \(2m+2=O(m)\) vertices and scans at most \(2m\) residual adjacency entries. Labels can be marked with a search number rather than clearing an \(n\)-entry array for every search; the array is initialized just once.
After BFS finds a path, following the predecessor pointers takes time proportional to its number of arcs. The path is simple because BFS visits each vertex at most once, and its vertices are among the non-isolated vertices just counted. Its length is therefore at most \(2m+1\). The bottleneck is the minimum positive residual capacity on the path. A second pass over the path subtracts that bottleneck from each used residual capacity and adds it to each paired reverse residual capacity. Finding and updating each paired entry takes constant time, so path recovery, bottleneck calculation, and residual updates together cost \(O(m)\).
Worked Example: Counting Searches and Updates
Let the directed network have \(V=\{s,a,b,t\}\) and arcs with capacities \(s\to a:3,\ s\to b:2,\ a\to b:1,\ a\to t:2,\ b\to t:3\). Thus \(n=4\), \(m=5\), and the residual representation has at most \(2m=10\) entries.
Fix the BFS neighbor order \(a,b\) at \(s\), \(b,t\) at \(a\), and \(t\) at \(b\). Initially all flows are zero. The first BFS has the following queue progression; each row gives the queue after processing the vertex named in the middle column.
| Search | Processed vertex | Queue afterwards | Newly discovered |
|---|---|---|---|
| 1 | \(s\) | \([a,b]\) | \(a,b\) |
| 1 | \(a\) | \([b,t]\) | \(t\) |
| 1 | \(b\) | \([t]\) | None |
BFS has found \(s\to a\to t\). Its residual capacities are \(3\) and \(2\), so the bottleneck is \(\min(3,2)=2\). Updating the path gives flows \(f(s,a)=2\), \(f(a,t)=2\), and residual capacities \(r(s,a)=1\), \(r(a,s)=2\), \(r(a,t)=0\), \(r(t,a)=2\). The flow value is now \(2\).
The next BFS starts with the same source. From \(s\), the positive forward arcs reach \(a,b\); processing \(a\) does not reach \(t\), since \(a\to t\) now has residual capacity \(0\). Processing \(b\) reaches \(t\) by \(b\to t\). The path is \(s\to b\to t\), with residual capacities \(2\) and \(3\), so its bottleneck is \(\min(2,3)=2\). The update gives \(f(s,b)=2\), \(f(b,t)=2\), and residual capacities \(r(s,b)=0\), \(r(b,s)=2\), \(r(b,t)=1\), \(r(t,b)=2\). The flow value is \(4\).
There is one more augmenting path: \(s\to a\to b\to t\). Its three residual capacities are \(1,1,1\), so the bottleneck is \(\min(1,1,1)=1\). After this update, \(f(s,a)=3\), \(f(a,b)=1\), \(f(b,t)=3\); the flow value is \(5\). A final BFS processes only \(s\): both arcs leaving \(s\) have residual capacity \(0\), so it cannot discover \(a\) or \(b\), and there is no path to \(t\).
Check: The flow value is \(f(s,a)+f(s,b)=3+2=5\), and the total flow entering \(t\) is \(f(a,t)+f(b,t)=2+3=5\). The cut with \(S=\{s\}\) has capacity \(c(s,a)+c(s,b)=3+2=5\), so this flow is maximum. There were three augmentations and four BFS calls, including the final unsuccessful search. A per-call bound proportional to \(m\) applies to all four calls.
Combining the Counts
For the total running-time analysis, the consequence we need is the number of augmentations. If \(A\) is that number, then \(A=O(nm)\). There is one BFS per augmentation and one final BFS that discovers no augmenting path, so the number of searches is \(A+1\). Each search and associated path update costs \(O(m)\). Thus, for \(m\ge1\), the search-and-update work is
When \(n\ge2\) and \(m\ge1\), \(m\le nm^2\), so this is \(O(nm^2)\). The one-time preprocessing costs \(O(n+m)\), also absorbed by \(O(nm^2)\) under those conditions. If \(m=0\), there is no augmenting path and the work is \(O(n)\) to initialize or inspect the network; the formula \(O(nm^2)\) is not intended to describe that degenerate input. The usual bound is stated for nontrivial networks with at least one arc.
Proof. Let \(A\) be the number of augmentations. By the Edmonds–Karp augmentation bound, \(A=O(nm)\). Each augmentation uses one BFS and one residual-path update, and each such combination takes \(O(m)\) time under the representation and preprocessing described above. The terminal unsuccessful BFS also costs \(O(m)\). Therefore all searches and updates take \(O((A+1)m)=O((nm+1)m)=O(nm^2+m)\). Since \(n\ge2\) and \(m\ge1\), \(m\le nm^2\), so this is \(O(nm^2)\). Preprocessing takes \(O(n+m)\); because \(m\ge1\), \(n+m\le n+nm^2\le2nm^2\), and it is absorbed by the same bound. Hence the total running time is \(O(nm^2)\). \(\square\)
Worked Example: A Path That Uses a Reverse Residual Arc
Let \(V=\{s,a,b,c,d,t\}\), with directed arcs of capacity \(1\): \(s\to a,\ s\to b,\ a\to c,\ a\to d,\ b\to c,\ c\to t,\ d\to t\). Thus \(n=6\), \(m=7\), and there are at most \(14\) paired residual entries. Use a BFS neighbor order that examines \(a\) before \(b\) at \(s\), and \(c\) before \(d\) at \(a\).
Initially BFS discovers \(a,b\) from \(s\), then discovers \(c,d\) from \(a\), and reaches \(t\) from \(c\). The first path is \(s\to a\to c\to t\), with residual capacities \(1,1,1\); its bottleneck is \(\min(1,1,1)=1\). The update sends one unit along those arcs, so \(f(s,a)=f(a,c)=f(c,t)=1\), and the paired reverse residual arc \(c\to a\) has capacity \(1\).
On the next search, \(s\to a\) has residual capacity \(0\), while \(s\to b\) has capacity \(1\). BFS reaches \(b\), then \(c\) via \(b\to c\). From \(c\), the forward arc \(c\to t\) has residual capacity \(0\), but the reverse residual arc \(c\to a\) has capacity \(1\), so BFS reaches \(a\). It then reaches \(d\) through \(a\to d\), and \(t\) through \(d\to t\). The path is \(s\to b\to c\to a\to d\to t\); its five residual capacities are all \(1\), so the bottleneck is \(\min(1,1,1,1,1)=1\).
The second update increases flow on \(s\to b,\ b\to c,\ a\to d,\ d\to t\) by \(1\) and uses the reverse arc \(c\to a\) to cancel the unit on \(a\to c\). Consequently \(f(a,c)\) returns to \(0\). The final positive original-arc flows are \(f(s,a)=1,\ f(s,b)=1,\ f(b,c)=1,\ f(a,d)=1,\ f(d,t)=1\); the flow value is \(2\). The cut \(S=\{s\}\) has capacity \(1+1=2\), so the flow is maximum. This example shows why residual storage must include reverse arcs and why an update can undo flow sent earlier.
Common Mistake: Counting Vertex Initialization Every Time
A careless analysis may say that each BFS costs \(O(n+m)\), multiply by \(O(nm)\) augmentations, and obtain \(O(n^2m+nm^2)\). It is not valid to discard the first term by assuming \(n\le m\): a network can have many isolated vertices. For instance, take \(n=100\) and \(m=3\). Then \(n^2m=100^2\cdot3=30{,}000\), whereas \(nm^2=100\cdot3^2=900\); the first expression is not bounded by a constant multiple of the second as \(n\) varies with \(m\) fixed.
The correction is to make the per-search accounting explicit. Isolated vertices cannot lie on a residual path, so remove them once, in \(O(n+m)\) preprocessing time. Thereafter, at most \(2m+2\) vertices can be reached, and search labels can be reused with timestamps rather than cleared across all \(n\) vertices at every BFS. Each BFS then takes \(O(m)\), and the one-time preprocessing is absorbed into the final bound when \(m\ge1\).
The estimate \(O(nm^2)\) is a worst-case upper bound, not a prediction of the exact number of operations on every network. The example with five arcs had only three augmentations, while the augmentation theorem allows a number proportional to \(nm\) in the worst case. The bound also depends on the stated representation and constant-time arithmetic model; different data structures or bit-level capacity costs require a separate analysis.
Worked Example: Isolated Vertices and Preprocessing
Let \(V=\{s,a,t,x_1,x_2,x_3,x_4,x_5\}\) and \(E=\{s\to a,\ a\to t\}\), with capacities \(4\) and \(3\), respectively. There are \(n=8\) vertices and \(m=2\) arcs. The five vertices \(x_1,\ldots,x_5\) are isolated and cannot occur on any residual path.
The one-time scan of the vertices and arcs costs \(O(n+m)=O(8+2)\). After ignoring the isolated vertices, the active vertex set is \(\{s,a,t\}\); the residual representation has at most \(2m=4\) entries. BFS finds \(s\to a\to t\), whose residual capacities are \(4\) and \(3\), so the bottleneck is \(\min(4,3)=3\). The update gives flow \(3\) on both arcs. In the final BFS, \(s\to a\) still has residual capacity \(1\), so \(a\) is reached, but \(a\to t\) has residual capacity \(0\); \(t\) is not reached and the algorithm stops.
Check: The resulting flow value is \(3\), and the cut \(S=\{s,a\}\) has capacity \(c(a,t)=3\), so the flow is maximum. The augmentation bound is \(O(nm)=O(8\cdot2)\), and the per-search bound is \(O(m)=O(2)\); the example uses one augmentation and two searches. The isolated vertices contribute to the one-time input cost, not to the work of each BFS.
Check Your Understanding
For each question, state the assumptions you use and show the relevant cost or residual-capacity calculation.
- Why does storing a paired reverse residual entry give at most \(2m\) residual entries?
- If there are \(A\) augmentations and each BFS plus update costs \(O(m)\), how many searches are performed, and what is the resulting total search-and-update cost?
- In a network with \(n=12\) and \(m=5\), evaluate the form \(nm^2\). How many residual entries are needed at most under paired storage?
- Explain why a path update takes \(O(m)\) time after isolated vertices are removed, even if the original network has many vertices.
- What is the separate running-time issue when \(m=0\), and why should it not be described by \(O(nm^2)\)?