Why Feasibility Must Be Checked
An augmenting path is useful only if updating the flow along it produces another allowable flow. The update is designed to send additional flow from the source to the sink, but a residual path can include reverse arcs: using one of these means reducing flow on an original arc. The signs of those changes matter. In particular, the two residual steps meeting at an internal vertex must balance, even when one of them cancels existing flow.
Throughout, a network is a finite directed graph \(G=(V,E)\) with distinct designated vertices \(s\) and \(t\), and a capacity function \(c:E\to[0,\infty)\). For an original arc \(e\), its flow is \(f(e)\). For a vertex \(v\), net outflow is the sum of flow on arcs leaving \(v\) minus the sum on arcs entering \(v\). A flow is feasible if it respects every capacity and has net outflow zero at each vertex other than \(s\) and \(t\). Its value \(|f|\) is the net outflow at \(s\). These conventions allow arcs entering \(s\) or leaving \(t\); the value is still defined as net outflow.
If the network has original arcs in both directions between a pair of vertices, their residual arcs are kept distinct by their original-arc labels. This avoids confusing an original arc with the reverse residual arc of another one. On a forward residual step, an update increases the flow on its recorded original arc. On a reverse residual step, it decreases the flow on the recorded original arc.
The Bottleneck Update
Let \(P\) be a residual path from \(s\) to \(t\). Its bottleneck \(\delta\) is the smallest residual capacity among its arcs. Because every arc of \(P\) has positive residual capacity and the path has finitely many arcs, \(\delta>0\). The update changes the original flow on each arc used by \(P\): add \(\delta\) for a forward residual step and subtract \(\delta\) for a reverse residual step. Every other original arc keeps its flow.
Proof. Write a residual step of \(P\) as \(u\to v\), and consider the original arc recorded by that step. If the step is forward, its residual capacity is \(c(e)-f(e)\), so \(\delta\le c(e)-f(e)\). The update sets \(f'(e)=f(e)+\delta\). Thus \(f'(e)\le c(e)\), while \(f'(e)\ge0\) because \(f(e)\ge0\). If the step is reverse, its residual capacity is \(f(e)\), so \(\delta\le f(e)\). The update sets \(f'(e)=f(e)-\delta\), which is nonnegative and no greater than \(c(e)\). Arcs not used by the path retain their original bounds. These arguments establish all capacity constraints.
It remains to check conservation and value. For any flow, let its net outflow at a vertex be \(b(v)\). A forward update on a residual step \(u\to v\) increases net outflow at \(u\) by \(\delta\) and decreases it at \(v\) by \(\delta\). For a reverse step \(u\to v\), the recorded original arc is \(v\to u\), and its flow decreases by \(\delta\). This decreases the original outflow at \(v\) by \(\delta\) and decreases the original inflow at \(u\) by \(\delta\). Equivalently, net outflow at \(u\) increases by \(\delta\) and net outflow at \(v\) decreases by \(\delta\). Thus, for either kind of residual step, the change is \(+\delta\) at its tail and \(-\delta\) at its head.
Along the path, each internal vertex is the head of one step and the tail of the next, so its total change in net outflow is \(-\delta+\delta=0\). The source \(s\) gains \(\delta\) in net outflow, and the sink \(t\) loses \(\delta\) in net outflow. Every vertex off the path has no change. Since the original flow conserved net outflow at every nonterminal vertex, the updated flow does also. Finally, the net outflow at \(s\) increases by \(\delta\), so \(|f'|=|f|+\delta\). This proves feasibility and the value formula. \(\square\)
The endpoint changes have the expected interpretation: the source sends an additional \(\delta\) units in net terms, and the sink receives an additional \(\delta\). The internal-vertex calculation is the key feasibility check. A reverse residual step does not create or destroy flow at an internal vertex by itself; its endpoint effects are exactly the ones needed for the path update to balance.
Worked Updates
Worked Example: An Augmentation Along Three Forward Arcs
Let the directed network have \(V=\{s,a,b,t\}\) and original arcs \(s\to a\), \(a\to b\), \(b\to t\). Their capacities and initial flows are:
| Original arc | Capacity | Initial flow |
|---|---|---|
| \(s\to a\) | 5 | 2 |
| \(a\to b\) | 4 | 2 |
| \(b\to t\) | 3 | 2 |
At \(a\), inflow is \(2\) and outflow is \(2\). At \(b\), inflow is \(2\) and outflow is \(2\). The source net outflow and sink net inflow are both \(2\), so the given flow is feasible and has value \(2\).
Take the residual path \(s\to a\to b\to t\). The forward residual capacities, computed as capacity minus flow, are \(5-2=3\), \(4-2=2\), and \(3-2=1\). Therefore \(\delta=\min\{3,2,1\}=1\). The update adds \(1\) on each of the three original arcs, giving flows \(3,3,3\), respectively.
Check: The updated flows satisfy \(3\le5\), \(3\le4\), and \(3\le3\), and are all nonnegative. At \(a\), inflow and outflow are both \(3\); at \(b\), they are also both \(3\). The source net outflow is \(3\), and the sink net inflow is \(3\), so the updated flow is feasible with value \(3=2+1\).
Worked Example: Cancelling Flow on a Reverse Residual Arc
Let \(V=\{s,a,b,t\}\) and let the original arcs, capacities, and initial flows be as follows:
| Original arc | Capacity | Initial flow |
|---|---|---|
| \(s\to a\) | 5 | 3 |
| \(s\to b\) | 4 | 2 |
| \(a\to b\) | 3 | 1 |
| \(b\to t\) | 4 | 3 |
| \(a\to t\) | 4 | 2 |
Initially, \(a\) has inflow \(3\) and outflow \(1+2=3\). Vertex \(b\) has inflow \(2+1=3\) and outflow \(3\). The source sends \(3+2=5\), and the sink receives \(3+2=5\). Hence the flow is feasible and has value \(5\).
Consider the residual path \(s\to b\to a\to t\). The step \(s\to b\) is forward, with residual capacity \(4-2=2\). The step \(b\to a\) is the reverse residual arc of the original \(a\to b\), with residual capacity \(1\). The step \(a\to t\) is forward, with residual capacity \(4-2=2\). Thus \(\delta=\min\{2,1,2\}=1\). The update increases \(f(s\to b)\) to \(3\), decreases \(f(a\to b)\) to \(0\), and increases \(f(a\to t)\) to \(3\). The other flows stay unchanged.
Check: The updated flows on \(s\to a,s\to b,a\to b,b\to t,a\to t\) are \(3,3,0,3,3\). Each is nonnegative and at most its capacity: \(3\le5\), \(3\le4\), \(0\le3\), \(3\le4\), and \(3\le4\). At \(a\), inflow remains \(3\) and outflow becomes \(0+3=3\). Reversing \(a\to b\) reduces \(a\)'s outflow by \(1\), while sending \(1\) on \(a\to t\) increases it by \(1\); these changes cancel. At \(b\), inflow is now \(3+0=3\), and outflow remains \(3\): the increase on \(s\to b\) is balanced by the decrease on \(a\to b\). The source sends \(3+3=6\), and the sink receives \(3+3=6\). The updated flow is feasible and has value \(6=5+1\).
Worked Example: A Bottleneck on the Last Step
Let \(V=\{s,a,b,t\}\), with original arcs \(s\to a\), \(s\to b\), \(a\to b\), \(a\to t\), and \(b\to t\). Specify the flow by listing each arc as capacity, flow: \(s\to a\) has \((5,2)\), \(s\to b\) has \((3,1)\), \(a\to b\) has \((4,1)\), \(a\to t\) has \((3,1)\), and \(b\to t\) has \((4,2)\).
Initially, \(a\) has inflow \(2\) and outflow \(1+1=2\). Vertex \(b\) has inflow \(1+1=2\) and outflow \(2\). The source sends \(2+1=3\), while the sink receives \(1+2=3\). The listed flows are within their capacities, so this is a feasible flow of value \(3\).
Use the residual path \(s\to a\to b\to t\). Its forward residual capacities are \(5-2=3\), \(4-1=3\), and \(4-2=2\). Hence its bottleneck is \(\delta=\min\{3,3,2\}=2\). The updated flows on these path arcs are \(4,3,4\), respectively; the flows on \(s\to b\) and \(a\to t\) remain \(1\) each.
Check: The five updated flows, in the order \(s\to a,s\to b,a\to b,a\to t,b\to t\), are \(4,1,3,1,4\). The capacity comparisons are \(4\le5\), \(1\le3\), \(3\le4\), \(1\le3\), and \(4\le4\); all flows are nonnegative. At \(a\), inflow \(4\) equals outflow \(3+1=4\). At \(b\), inflow \(1+3=4\) equals outflow \(4\). The source sends \(4+1=5\), and the sink receives \(1+4=5\). Thus the updated flow is feasible, and its value is \(5=3+2\).
Common Mistakes and the Feasibility Checklist
A frequent sign error is to treat a reverse residual step \(u\to v\) as though it were an increase on the original arc \(u\to v\). It is not: it decreases flow on the original arc \(v\to u\). For example, in the second worked example, the residual step \(b\to a\) reduces the flow on \(a\to b\). At \(a\), this reduces outflow by \(1\); the next residual step \(a\to t\) increases outflow by \(1\). At \(b\), the first step \(s\to b\) increases inflow by \(1\), and reducing the flow on \(a\to b\) decreases inflow by \(1\). Both internal vertices remain balanced.
A wrong calculation would say that the reverse step \(b\to a\) increases net outflow at \(a\) by \(1\). The correction is to track the original arc: reducing \(a\to b\) decreases \(a\)'s outflow, so \(a\)'s net outflow changes by \(-1\), not \(+1\). The residual-step viewpoint gives the same answer: the residual arc's head is \(a\), so its contribution to \(a\)'s net-outflow change is \(-\delta\).
For a proposed augmentation, check the following points in order:
- Each residual step has positive residual capacity, and its recorded original arc is identified.
- The bottleneck is the minimum of those residual capacities, so it is positive and no larger than any one of them.
- A forward step adds at most the unused capacity; a reverse step subtracts at most the existing flow.
- Every internal path vertex has one path step entering and one leaving, whose net-outflow changes cancel.
- The source net outflow rises by the bottleneck, and the sink net outflow falls by the same amount.
These checks establish feasibility without requiring the updated flow to use only original forward arcs: reverse residual steps are legitimate precisely because their updates remove existing flow while respecting its lower bound of zero. The next question is how an entire flow can be represented in terms of paths and cycles; that is a different structural result from the local feasibility argument proved here.
Check Your Understanding
For each question, keep track of changes on original arcs, including when a residual step is reverse.
- On a forward residual arc of capacity \(c(e)-f(e)\), why does an update by the path bottleneck preserve both bounds \(0\le f'(e)\le c(e)\)?
- If a residual step \(u\to v\) is the reverse of an original arc \(v\to u\), state the change in net outflow at \(u\) and at \(v\).
- In the second worked example, recompute the updated inflow and outflow at \(b\). Which two arc-flow changes account for the balance?
- Explain why the change in net outflow at an internal path vertex is zero, regardless of whether either incident residual step is forward or reverse.
- Why must the source-to-sink path have positive bottleneck before the value-increase conclusion applies?