Why a Flow May Need to Be Undone
When a flow is sent along an edge, it uses some of that edge’s capacity. A later choice of route may reveal that part of this flow would be better sent elsewhere. A residual network records both possibilities: adding flow along an original arc that still has spare capacity, and canceling flow previously assigned to an original arc. The second possibility is represented by a reverse residual arc.
Here a network is a finite directed graph \(G=(V,E)\), with distinct source \(s\) and sink \(t\), and a nonnegative capacity \(c(e)\) on every arc \(e\in E\). We assume there are no parallel arcs in the examples. A flow assigns a number \(f(e)\) to each original arc, with \(0\le f(e)\le c(e)\). At every vertex other than \(s\) and \(t\), total inflow equals total outflow. The flow value is the net outflow from \(s\).
If a network has original arcs in both directions between two vertices, keep track of which original arc gives rise to each residual arc. For example, the residual arc \(v\to u\) arising from \(u\to v\) is a cancellation option, while an original arc \(v\to u\) has its own forward residual capacity. These are different sources of residual capacity even though their directions agree.
What Cancellation Means
Suppose \(e=(u,v)\) currently carries \(f(e)\) units. Sending \(x\) units along its reverse residual arc \(v\to u\) means reducing the original flow on \(e\) by \(x\). This is possible only when \(x\le f(e)\); otherwise the updated original flow would be negative. Cancellation restores the same amount of forward residual capacity on \(u\to v\), since that capacity is \(c(e)-f(e)\) before cancellation and \(c(e)-(f(e)-x)\) afterwards.
Proof. Adding \(x\) units to \(e\) gives flow \(f(e)+x\), which satisfies the capacity bound exactly when \(f(e)+x\le c(e)\), or \(x\le c(e)-f(e)\). Decreasing the flow by \(x\) gives \(f(e)-x\), which is nonnegative exactly when \(x\le f(e)\). Thus the stated quantities are the greatest allowable changes in the two directions. After canceling \(x\), the forward residual capacity is \(c(e)-(f(e)-x)=c(e)-f(e)+x\), an increase of \(x\). \(\square\)
This proposition explains the number on a reverse residual arc: it is not a new supply of flow. It is the amount of existing flow that can be taken back. At the endpoints, canceling \(x\) decreases the flow leaving \(u\) and decreases the flow entering \(v\), each by \(x\). When cancellation is part of a rerouting, other changes on the route can compensate for these endpoint changes.
Worked Example: Reading a Reverse Residual Capacity
Let the network have \(V=\{s,t\}\), \(E=\{st\}\), and capacity \(c(st)=5\). Suppose the current flow is \(f(st)=3\). The flow is feasible: \(0\le3\le5\), and its value is \(3\).
The forward residual capacity is \(5-3=2\), so at most \(2\) more units can be sent from \(s\) to \(t\) on the original arc. The reverse residual arc \(t\to s\) has capacity \(3\), so at most \(3\) units can be canceled. If we cancel \(x=2\) units, the updated original flow is \(3-2=1\). Its forward residual capacity is now \(5-1=4\), and its reverse residual capacity is \(1\).
Check: The updated flow still satisfies \(0\le1\le5\). The forward residual capacity increased by \(2\), from \(2\) to \(4\), and the reverse residual capacity decreased by \(2\), from \(3\) to \(1\). The updated flow value is \(1\), exactly \(2\) less than before.
Rerouting Through a Reverse Arc
A reverse residual arc can be useful when an earlier flow choice occupies an edge needed by a better route. A residual route may travel forward on some original arcs and backward on others. Traveling backward cancels flow on the corresponding original arcs; it does not require the original network to contain an arc in that direction.
The following example shows the central mechanism. Initially, the only positive flow uses the middle arc \(a\to b\). To send a second unit to the sink, the rerouting goes from \(b\) back to \(a\) in the residual network. That step cancels the existing flow on \(a\to b\), allowing the two units to use separate routes.
Worked Example: Canceling Flow to Reach a Larger Value
Let \(V=\{s,a,b,t\}\) and \(E=\{sa,sb,ab,at,bt\}\). Every arc has capacity \(1\). Initially set \(f(sa)=f(ab)=f(bt)=1\) and \(f(sb)=f(at)=0\). The initial flow is feasible: at \(a\), inflow and outflow are both \(1\); at \(b\), inflow and outflow are both \(1\). Its value is \(1\), since the only positive flow leaving \(s\) is on \(sa\).
The residual capacities relevant to the rerouting are:
| Residual arc | Why it is present | Residual capacity |
|---|---|---|
| \(s\to b\) | Forward arc for \(sb\) | \(1-0=1\) |
| \(b\to a\) | Reverse arc for \(ab\) | \(f(ab)=1\) |
| \(a\to t\) | Forward arc for \(at\) | \(1-0=1\) |
Send \(1\) unit along the residual route \(s\to b\to a\to t\). The step \(b\to a\) is the reverse residual arc for \(ab\), so it cancels the original unit on \(ab\). The other two steps add one unit to \(sb\) and \(at\). The updated original flows are \(f(sa)=1\), \(f(sb)=1\), \(f(ab)=0\), \(f(at)=1\), and \(f(bt)=1\).
Check: Every flow is between \(0\) and its capacity \(1\). At \(a\), inflow is \(f(sa)=1\), and outflow is \(f(ab)+f(at)=0+1=1\). At \(b\), inflow is \(f(sb)+f(ab)=1+0=1\), and outflow is \(f(bt)=1\). The sink receives \(f(at)+f(bt)=1+1=2\), while the source sends \(f(sa)+f(sb)=1+1=2\). Thus the updated flow is feasible and has value \(2\), greater than the initial value \(1\).
The reverse step did not simply erase flow and leave the rest unchanged. If we had only reduced \(f(ab)\) from \(1\) to \(0\), then the intermediate assignment would fail conservation at \(a\) and \(b\). The complete rerouting also adds flow on \(sb\) and \(at\), so the updated assignment balances at both vertices. The later material on flow augmentation treats this kind of update in general; here the essential point is the meaning of the cancellation step.
Proof. By the definition of a reverse residual arc, using it to cancel \(x\) units changes the original flow from \(f(e)\) to \(f(e)-x\). The condition \(x\le f(e)\) ensures this flow remains nonnegative. The old forward residual capacity is \(c(e)-f(e)\); the new one is \(c(e)-(f(e)-x)=c(e)-f(e)+x\), so it increases by \(x\). The old reverse residual capacity is \(f(e)\); the new one is \(f(e)-x\), so it decreases by \(x\). \(\square\)
Worked Example: Partial Cancellation in a Larger Network
Let \(V=\{s,a,b,t\}\) and \(E=\{sa,ab,bt,sb,at\}\), with capacities \(c(sa)=3\), \(c(ab)=3\), \(c(bt)=3\), \(c(sb)=2\), and \(c(at)=2\). Start with \(f(sa)=f(ab)=f(bt)=3\), \(f(sb)=f(at)=0\). This is feasible: \(a\) receives and sends \(3\), \(b\) receives and sends \(3\), and the flow value is \(3\).
Consider the residual route \(s\to b\to a\to t\). Its residual capacities are \(2-0=2\) on \(sb\), \(f(ab)=3\) on the reverse residual arc \(b\to a\), and \(2-0=2\) on \(at\). Thus \(2\) units can be sent along this route without canceling more flow than \(ab\) carries. The update adds \(2\) to \(sb\), cancels \(2\) on \(ab\), and adds \(2\) to \(at\). The new flows are \(f(sa)=3\), \(f(ab)=1\), \(f(bt)=3\), \(f(sb)=2\), and \(f(at)=2\).
Check: The updated flows satisfy their bounds: \(3\le3\) on \(sa,bt\), \(1\le3\) on \(ab\), \(2\le2\) on \(sb,at\), and all are nonnegative. At \(a\), inflow is \(3\) and outflow is \(1+2=3\). At \(b\), inflow is \(2+1=3\) and outflow is \(3\). The source sends \(3+2=5\), and the sink receives \(3+2=5\), so the new flow value is \(5\). On \(ab\), the forward residual capacity changed from \(3-3=0\) to \(3-1=2\), matching the \(2\) units canceled.
Common Pitfalls
Mistake: treating a reverse residual arc as an original arc. In the first rerouting example, the arc \(b\to a\) does not belong to the original edge set \(E=\{sa,sb,ab,at,bt\}\). It appears in the residual network because \(f(ab)=1\). Calling it an original arc would misdescribe the network and could lead to incorrectly adding flow to a nonexistent edge. The correct update is \(f(ab)=1-1=0\).
Mistake: setting reverse residual capacity to unused capacity. In the capacity-\(5\) example, a common incorrect calculation is to give the reverse arc capacity \(5-3=2\). That value is the forward residual capacity. The reverse residual capacity is the flow already present, \(f(st)=3\). The two directions answer different questions: how much more can be added, and how much can be canceled.
Mistake: canceling more than the current flow. If an original arc carries \(1\) unit, its reverse residual capacity is \(1\), not its full original capacity. Attempting to cancel \(2\) would produce flow \(1-2=-1\), violating nonnegativity. Always compute reverse capacity from the current flow, since it changes after each update.
Reverse residual arcs make flow routing flexible: an earlier assignment is not permanent. They permit local corrections that can free capacity for a better overall route. The key bookkeeping is always tied to the original arc: a forward residual step increases its flow, while a reverse residual step decreases it.
Check Your Understanding
For each question, distinguish carefully between original arcs and residual arcs, and verify any proposed update against the capacity bounds.
- An original arc has capacity \(7\) and currently carries \(4\) units. What are its forward and reverse residual capacities?
- An original arc carries \(2\) units. Can \(3\) units be sent along its reverse residual arc? Explain using the updated flow bound.
- In the network of the rerouting example, why is \(b\to a\) available in the residual network even though it is not in the original edge set?
- If \(e=(u,v)\) has capacity \(c(e)\) and flow \(f(e)\), derive the forward residual capacity after canceling \(x\) units, where \(0\le x\le f(e)\).
- Explain why canceling flow on one arc alone may break conservation, even though the cancellation respects that arc’s capacity bounds.