Why Count Critical Arcs?
Edmonds–Karp repeatedly finds a shortest augmenting path in the residual network and augments the flow along it. The number of augmentations is not bounded just by the fact that each augmentation changes the flow: capacities may be large, and an arc that becomes saturated can later regain positive residual capacity. The key is to count how often this can happen to one fixed directed residual arc.
Throughout, \(G=(V,E)\) is a finite directed network with source \(s\), sink \(t\), and nonnegative capacities. A residual arc records a possible flow adjustment. For an original arc \(e=(x,y)\) with capacity \(c(e)\) and current flow \(f(e)\), its forward residual capacity is \(c(e)-f(e)\), and its reverse residual capacity is \(f(e)\). A residual arc is available when its residual capacity is positive. To keep identities unambiguous, residual arcs are labelled by the original arc and whether they are forward or reverse. This matters when the original network has arcs in both directions between two vertices.
All distances below are measured in the residual network just before the relevant augmentation. Write \(d(s,v)\) for the length of a shortest residual path from \(s\) to \(v\), and set \(d(s,v)=\infty\) if \(v\) is unreachable. A shortest path can be taken to have no repeated vertices, so any finite distance is at most \(|V|-1\).
The Distance Change Behind the Bound
We use the residual-distance monotonicity result established in the earlier material on residual distances in Edmonds–Karp: from one augmentation to the next, the distance from \(s\) to any vertex never decreases. In precise terms, if \(d_i(v)\) is the residual distance before augmentation \(i\), then \(d_{i+1}(v)\ge d_i(v)\), with \(\infty\) larger than every finite distance. The proof of that result belongs to the earlier treatment; here we use it to bound repeated critical events.
Proof. Let the first critical event occur when the distances are \(d_i\). Since \(a=(x,y)\) lies on a shortest \(s\)-to-\(t\) path, the part of that path from \(s\) to \(y\) is also shortest to \(y\). Therefore \(d_i(y)=d_i(x)+1\). The augmentation saturates \(a\), so that labelled residual arc is unavailable afterward.
For \(a\) to be critical again, its residual capacity must first become positive. The only operation that increases the residual capacity of \(a\) is using its reverse residual arc \(a^{-1}=(y,x)\) on an augmentation. Consider the first such use after the first critical event, and let the distances just before that augmentation be \(d_j\). Because \(a^{-1}\) lies on a shortest augmenting path, \(d_j(x)=d_j(y)+1\). By distance monotonicity, \(d_j(y)\ge d_i(y)\). Combining these facts gives
The distance from \(s\) to \(x\) cannot decrease after that augmentation either. Hence, when \(a\) is critical again, its tail \(x\) has distance at least \(d_i(x)+2\). \(\square\)
The orientation is important: when \(x\to y\) is saturated, it is the reverse arc \(y\to x\) that must be used to restore capacity. On a shortest path, that reverse arc moves from distance \(d(y)\) to distance \(d(x)=d(y)+1\), forcing the tail’s distance upward.
Worked Example: One Critical Event on a Shortest Path
Let the directed network have \(V=\{s,a,b,t\}\), with capacities \(c(sa)=3\), \(c(ab)=2\), and \(c(bt)=4\), and no other original arcs. Start with zero flow. Its only \(s\)-to-\(t\) path is \(s,a,b,t\), of length \(3\), so it is a shortest augmenting path.
The residual capacities along the path are \(3,2,4\). Thus the bottleneck is \(\min\{3,2,4\}=2\). Augmenting by \(2\) changes the three flows to \(f(sa)=2\), \(f(ab)=2\), and \(f(bt)=2\). The forward residual capacities become \(3-2=1\), \(2-2=0\), and \(4-2=2\), respectively. Therefore \(ab\) is critical; \(sa\) and \(bt\) are not.
The reverse residual capacities created are \(2\) on \(a\to s\), \(2\) on \(b\to a\), and \(2\) on \(t\to b\). The distances before augmentation were \(d(s,a)=1\), \(d(s,b)=2\), and \(d(s,t)=3\). In particular, for the critical arc \(a\to b\), its head distance was exactly one more than its tail distance.
Check: At the end, the flow value is \(2\), because \(2\) units leave \(s\) on \(sa\). Flow conservation holds at \(a\) and \(b\): each has \(2\) units entering and \(2\) leaving. The forward residual capacity of \(ab\) is \(2-2=0\), confirming that it was saturated.
Each Residual Arc Is Critical Only O(V) Times
Proof. Fix a labelled residual arc \(a=(x,y)\), and suppose it is critical \(q\ge1\) times. Let \(r\) be the distance from \(s\) to \(x\) at its first critical event. Every such event occurs on an augmenting path, so \(x\) is reachable from \(s\) at that time and \(0\le r\le n-1\). By the Lemma, between consecutive critical events the distance to \(x\) increases by at least \(2\). Consequently, at the \(q\)-th event the distance to \(x\) is at least \(r+2(q-1)\). It is finite and at most \(n-1\), so
If the arc is never critical, the bound holds because its count is zero. These cases cover every fixed residual arc, proving the result. \(\square\)
This is a bound on one labelled directed residual arc, not on all arcs together. The network may contain many such arcs. The significance is that a single arc cannot repeatedly become a bottleneck on shortest paths without its tail moving farther from the source.
Worked Example: Evaluating the Bound for Seven Vertices
Suppose \(n=7\) and a fixed residual arc first becomes critical when its tail \(x\) has distance \(r=1\) from \(s\). Every later critical event must have tail distance at least \(2\) more than the previous one. The possible distances for its critical events are therefore at least \(1,3,5,\ldots\).
A finite distance is at most \(n-1=6\). Thus the first three lower bounds, \(1\), \(3\), and \(5\), fit within the limit, while a fourth would require distance at least \(7\), which exceeds \(6\). The sharper bound from the proof gives \(\lfloor(7-1-1)/2\rfloor+1=\lfloor5/2\rfloor+1=3\) critical events. The general theorem’s bound is \(\lfloor(7+1)/2\rfloor=4\), which is valid but does not use the fact that the first distance was \(1\).
Check: The upper endpoint for a finite distance is \(7-1=6\). The three listed lower bounds satisfy \(1\le6\), \(3\le6\), and \(5\le6\); the next is \(7>6\). Thus four events are ruled out when the first distance is \(1\).
Why Residual Arc Identity Matters
If an original network has arcs in both directions between two vertices, residual arcs with the same ordered endpoints may come from different original arcs. Their residual capacities must not be confused. For example, the forward residual arc of an original \(u\to v\) arc and the reverse residual arc of an original \(v\to u\) arc both point from \(u\) to \(v\), but only the reverse arc associated with the first original arc restores capacity to that first arc. The theorem applies to each labelled arc separately.
Worked Example: Distinct Residual Arcs with the Same Direction
Let \(V=\{s,u,v,t\}\). The original directed arcs and capacities are \(s\to u\) with capacity \(2\), \(u\to v\) with capacity \(3\), \(v\to u\) with capacity \(1\), and \(v\to t\) with capacity \(2\). Begin with zero flow. The path \(s,u,v,t\) has length \(3\), and is the only \(s\)-to-\(t\) path, so it is shortest. Its residual capacities are \(2,3,2\), giving bottleneck \(\min\{2,3,2\}=2\).
After augmenting by \(2\), the flows on \(s\to u\), \(u\to v\), \(v\to u\), and \(v\to t\) are \(2,2,0,2\). The forward residual capacity of \(u\to v\) from the original \(u\to v\) arc is \(3-2=1\); its reverse residual capacity \(v\to u\) is \(2\). Separately, the forward residual capacity of the original \(v\to u\) arc is \(1-0=1\). Thus there are two distinct residual arcs from \(v\) to \(u\), with capacities \(2\) and \(1\).
The critical arcs on the path were \(s\to u\), whose residual capacity became \(2-2=0\), and \(v\to t\), whose residual capacity became \(2-2=0\). The arc \(u\to v\) was not critical, since its residual capacity is \(3-2=1\). The flow value is \(2\). To check maximality independently, take the cut with source side \(\{s\}\): the only original arc leaving it is \(s\to u\), so the cut capacity is \(2\). No flow can have value greater than this cut capacity, and the displayed flow has value \(2\).
Common Pitfall
A common error is to say that the tail distance rises by only \(1\) before an arc can be critical again. That misses the extra step across the reverse arc. For example, suppose \(d_i(x)=2\) and \(d_i(y)=3\) when \(x\to y\) is critical. When the reverse arc \(y\to x\) is later used on a shortest path, its endpoints must satisfy \(d_j(x)=d_j(y)+1\). Monotonicity gives \(d_j(y)\ge3\), so \(d_j(x)\ge4\), not \(3\). The increase from the earlier tail distance \(2\) is at least \(2\).
Another error is to claim that a saturated residual arc can never be critical again. Saturation only removes that particular residual direction temporarily; a later augmentation may use its reverse direction and restore positive residual capacity. The distance argument—not permanent disappearance—is what limits how often it can recur.
The per-arc bound is useful because it turns a global question about the number of augmentations into a count of events attached to individual residual arcs. The next step in the Edmonds–Karp analysis combines this fact across the residual arcs of the network to bound the total number of augmentations.
Check Your Understanding
Use the definitions and distance argument above to answer these questions.
- In a network with \(n=9\), a fixed residual arc is first critical with tail distance \(r=2\). What is the strongest count bound obtained directly from the proof?
- Why must the reverse of a saturated labelled residual arc be used before that same arc can become available again?
- At a critical event for \(x\to y\), why must \(d(s,y)=d(s,x)+1\)?
- Explain why two residual arcs with the same ordered endpoints can still be distinct arcs.
- Give the distance inequality that rules out a rise of only \(1\) between consecutive critical events.