From a Residual Path to a Flow Update
A source-to-sink path in a residual network describes a possible change to the current flow. Along a forward residual arc, the flow on its original arc can increase. Along a reverse residual arc, some existing flow can be cancelled. The amount of change must respect every residual capacity on the chosen path, so the smallest of those capacities determines how much can be sent.
Throughout, a network is a finite directed graph with distinct source \(s\) and sink \(t\), and each original arc \(e\) has a nonnegative capacity \(c(e)\). A flow \(f\) assigns a number to each original arc, with \(0\le f(e)\le c(e)\). At each vertex other than \(s\) and \(t\), total inflow equals total outflow. The flow value is the net outflow from \(s\).
A forward residual arc records unused capacity; a reverse residual arc records flow that could be cancelled. In particular, the reverse residual capacity is the current flow, not the original capacity. An augmenting path is a directed path from \(s\) to \(t\) in the residual network. We take a path to have no repeated vertices. Every residual arc on it has positive capacity.
The path is fixed when taking this minimum. The bottleneck is the largest amount that can be sent along that path in one update without exceeding a residual capacity. It does not, by itself, say that the whole network has reached its maximum possible flow.
Why the Minimum Is the Limiting Amount
Proof. If an amount \(x\ge0\) is sent along the path, the residual capacity remaining on its \(i\)th arc is \(r_i-x\). All used residual capacities remain nonnegative exactly when \(r_i-x\ge0\) for every \(i\), which is equivalent to \(x\le r_i\) for every \(i\). Thus \(x\le\min_i r_i\). The value \(x=\min_i r_i\) satisfies every one of these inequalities, so it is permissible and is the largest permissible amount. \(\square\)
The update has a simple local effect on a residual pair. If \(e=(u,v)\) is traversed forward by \(\Delta\), its flow becomes \(f(e)+\Delta\). Its forward residual capacity decreases by \(\Delta\), and its reverse residual capacity increases by \(\Delta\). If the path uses \(e^-\), the flow becomes \(f(e)-\Delta\): the reverse residual capacity decreases by \(\Delta\), while the forward residual capacity increases by \(\Delta\).
For example, on a forward traversal the new residual capacities are \(c(e)-(f(e)+\Delta)=(c(e)-f(e))-\Delta\) and \(f(e)+\Delta\). On a reverse traversal they are \(c(e)-(f(e)-\Delta)=(c(e)-f(e))+\Delta\) and \(f(e)-\Delta\). Since \(\Delta\) is at most the capacity of every used residual arc, none of the traversed residual capacities becomes negative. This establishes the arc-by-arc arithmetic of the update. It does not replace the separate argument that the updated flow satisfies all conservation equations.
Worked Updates
Worked Example: A Forward-Only Path
Consider the directed network with \(V=\{s,a,b,t\}\), source \(s\), sink \(t\), and original arcs \(E=\{(s,a),(a,b),(b,t),(a,t)\}\). Their capacities are \(c(s,a)=5\), \(c(a,b)=2\), \(c(b,t)=4\), and \(c(a,t)=3\). Start with zero flow on every arc, and choose the path \(s,a,b,t\).
The residual capacities on this path are \(5-0=5\), \(2-0=2\), and \(4-0=4\). Therefore $$ \Delta=\min\{5,2,4\}=2. $$ All three traversals are forward, so add \(2\) to the flow on each corresponding original arc.
| Original arc | Flow before | Residual before | Flow after | Forward residual after |
|---|---|---|---|---|
| \((s,a)\) | 0 | \(5-0=5\) | \(0+2=2\) | \(5-2=3\) |
| \((a,b)\) | 0 | \(2-0=2\) | \(0+2=2\) | \(2-2=0\) |
| \((b,t)\) | 0 | \(4-0=4\) | \(0+2=2\) | \(4-2=2\) |
Check: The three residual capacities after the update are \(3,0,2\), each equal to its earlier value minus \(2\). The arc \((a,b)\) is saturated, so this particular path has no remaining forward residual capacity through that arc. The reverse residual capacities on the three used arcs are now \(2,2,2\), equal to their updated flows.
Worked Example: Cancelling Flow on a Reverse Arc
Let \(V=\{s,a,b,t\}\) and \(E=\{(s,a),(a,b),(b,t),(s,b),(a,t)\}\), with source \(s\) and sink \(t\). Give the arcs the following capacities and current flows:
| Arc | Capacity | Current flow | Residual capacities |
|---|---|---|---|
| \((s,a)\) | 3 | 3 | forward \(3-3=0\), reverse \(3\) |
| \((a,b)\) | 2 | 1 | forward \(2-1=1\), reverse \(1\) |
| \((b,t)\) | 3 | 2 | forward \(3-2=1\), reverse \(2\) |
| \((s,b)\) | 2 | 1 | forward \(2-1=1\), reverse \(1\) |
| \((a,t)\) | 4 | 2 | forward \(4-2=2\), reverse \(2\) |
This is a feasible starting flow: at \(a\), inflow \(3\) equals outflow \(1+2=3\); at \(b\), inflow \(1+1=2\) equals outflow \(2\). The source sends \(3+1=4\), and the sink receives \(2+2=4\). Choose the residual path \(s\to b\to a\to t\). Its middle step \(b\to a\) is the reverse residual arc of the original arc \((a,b)\).
The path capacities are \(2-1=1\) on the forward residual arc from \(s\) to \(b\), \(1\) on the reverse residual arc of \((a,b)\), and \(4-2=2\) on the forward residual arc from \(a\) to \(t\). Hence \(\Delta=\min\{1,1,2\}=1\). Update the three original arcs as follows:
- Traverse \((s,b)\) forward: \(f(s,b)=1+1=2\).
- Traverse \((a,b)\) backward: \(f(a,b)=1-1=0\).
- Traverse \((a,t)\) forward: \(f(a,t)=2+1=3\).
The unchanged flows are \(f(s,a)=3\) and \(f(b,t)=2\). The updated forward residual capacities on the changed arcs are \(2-2=0\) for \((s,b)\), \(2-0=2\) for \((a,b)\), and \(4-3=1\) for \((a,t)\). Their reverse residual capacities are respectively \(2\), \(0\), and \(3\). The updated source outflow is \(3+2=5\), and the updated sink inflow is \(2+3=5\).
Check: The reverse traversal reduced \(f(a,b)\) from \(1\) to \(0\), exactly exhausting the reverse residual capacity on that step. Its forward residual capacity rose from \(1\) to \(2\). Thus the reverse step cancels one unit of existing flow rather than sending an extra unit on \((a,b)\).
Worked Example: Tied Bottlenecks and a Path-Specific Limit
Let \(V=\{s,x,y,t\}\), with source \(s\), sink \(t\), and directed arcs \(E=\{(s,x),(x,t),(s,y),(y,t)\}\). Set \(c(s,x)=3\), \(c(x,t)=3\), \(c(s,y)=5\), and \(c(y,t)=4\), with zero flow on every arc. On the chosen path \(s,x,t\), the two residual capacities are \(3-0=3\) and \(3-0=3\), so \(\Delta=\min\{3,3\}=3\).
Increase \(f(s,x)\) and \(f(x,t)\) from \(0\) to \(0+3=3\). Their forward residual capacities become \(3-3=0\) and \(3-3=0\); their reverse residual capacities become \(3\) and \(3\). The other two flows remain zero, with forward residual capacities \(5-0=5\) and \(4-0=4\).
Check: Both arcs on the chosen path are saturated, so that path cannot carry another positive augmentation. But the different path \(s,y,t\) still has residual capacities \(5\) and \(4\), with bottleneck \(\min\{5,4\}=4\). The bottleneck of one path is therefore a limit for that path, not a certificate that no other augmenting path exists.
Common Mistakes and a Reliable Routine
Mistake: use original capacities instead of residual capacities. In the reverse-arc example, the raw capacities along \(s\to b\to a\to t\), if one ignores direction and current flow, are \(2,2,4\). Taking their minimum gives \(2\). But the residual capacities in the actual traversal directions are \(1,1,2\), so sending \(2\) would exceed the reverse residual capacity \(1\) and would require reducing \(f(a,b)=1\) by \(2\), giving a negative flow.
Correction: Determine the residual capacity of each labelled arc in the direction it is traversed. For \(b\to a\), that capacity is \(f(a,b)=1\), not \(c(a,b)=2\). The correct bottleneck is \(\min\{1,1,2\}=1\).
A dependable calculation follows this order:
- Write the directed residual path, marking each step as forward or reverse and identifying its original arc.
- Compute the residual capacity of every step from the current flow.
- Take the minimum of those values; do not sum them or substitute original capacities.
- Apply the same amount to every path step, adding on forward traversals and subtracting on reverse traversals.
- Recompute the affected residual pairs to check that the used capacities fell by the update amount and none became negative.
The update is simultaneous: the bottleneck is calculated from the residual capacities before the change, and the same \(\Delta\) is then applied to each step. Recording the direction of every step prevents the most consequential error—adding flow when a reverse residual arc requires cancellation.
Check Your Understanding
For each question, distinguish the original arcs from their labelled residual arcs and use the flow values stated.
- An augmenting path has residual capacities \(6,2,5,4\). What is its bottleneck, and which path steps become saturated after augmentation by that amount?
- An original arc \(u\to v\) has capacity \(7\) and current flow \(3\). State the capacities of its forward and reverse residual arcs. What are they after a reverse traversal by \(2\)?
- A path contains a forward residual arc of capacity \(4\) and a reverse residual arc of capacity \(1\). Explain why an update of \(2\) is not allowed, even if both original capacities are at least \(2\).
- Can a path bottleneck alone show that the flow is maximum? Give a reason using a network with another source-to-sink path.
- For an original arc of capacity \(5\) carrying flow \(5\), state both residual capacities and explain which direction, if either, can be used in the residual network.