The Residual Network as a Test for Maximality
A feasible flow can often be increased by sending more flow along a route from the source to the sink. The route need not use only unused capacity in the original direction: if some existing flow can be cancelled, a reverse residual arc records that option. The residual network gathers both possibilities. The augmenting path characterization says that these local possibilities give an exact test for whether a feasible flow is already maximum.
Throughout, let \((G,c,s,t)\) be a finite directed network with distinct source \(s\) and sink \(t\), and nonnegative finite capacities \(c(e)\) on its arcs. A flow \(f\) assigns a real number \(f(e)\) to each arc, satisfies \(0\le f(e)\le c(e)\), and obeys flow conservation at every vertex other than \(s\) and \(t\). Its value \(|f|\) is the net flow out of \(s\). A flow is maximum if no feasible flow in the same network has strictly greater value.
The forward residual capacity measures how much more flow can be sent on \(e\). The reverse residual capacity measures how much flow can be removed from \(e\). A residual \(s\)-\(t\) path is a path from \(s\) to \(t\) whose every arc has strictly positive residual capacity. Its bottleneck is the smallest residual capacity on the path, so the bottleneck is positive.
The Augmenting Path Characterization
The two directions have different roles. A residual path gives a concrete way to improve a flow. Conversely, if a better feasible flow existed, the differences between it and the current flow would provide enough residual capacity to reach the sink.
Proof. First suppose there is a residual \(s\)-\(t\) path \(P\). Let \(\delta\) be its bottleneck, the minimum of the residual capacities along \(P\); since every capacity on the path is positive, \(\delta>0\). For each forward residual arc on \(P\), increase the corresponding original flow by \(\delta\). For each reverse residual arc, decrease the corresponding original flow by \(\delta\). The residual capacity bounds ensure that the updated flow stays between zero and the original capacity on every affected arc. At each internal vertex of the path, one path arc enters and one leaves, so the changes preserve conservation there. The path starts at \(s\) and ends at \(t\), so the net flow out of \(s\) increases by \(\delta\). Thus the update is feasible and has value \(|f|+\delta>|f|\). Hence \(f\) is not maximum.
For the converse, suppose \(f\) is not maximum. Then there is a feasible flow \(g\) with \(|g|>|f|\). For every original arc \(e=(u,v)\), compare \(g(e)\) with \(f(e)\). If \(g(e)>f(e)\), assign amount \(g(e)-f(e)\) to the forward residual arc from \(u\) to \(v\). This amount is at most \(c(e)-f(e)\), since \(g(e)\le c(e)\). If \(g(e)<f(e)\), assign amount \(f(e)-g(e)\) to the reverse residual arc from \(v\) to \(u\). This amount is at most \(f(e)\), since \(g(e)\ge0\). If the flows agree, assign zero. Denote these nonnegative amounts by \(x\); each is within the corresponding residual capacity.
For a vertex \(v\), define the divergence of \(x\) to be the total assigned amount leaving \(v\) minus the total assigned amount entering \(v\). Each difference \(g(e)-f(e)\) contributes exactly its signed change to the divergence at the endpoints of \(e\), whether it is represented by a forward or reverse residual arc. Therefore the divergence of \(x\) at every vertex is the divergence of \(g\) minus the divergence of \(f\). Both flows conserve flow at every vertex other than \(s,t\), so \(x\) has divergence zero at every such vertex. At \(s\), its divergence is \(|g|-|f|>0\).
Let \(R\) be the vertices reachable from \(s\) using residual arcs to which \(x\) assigns a strictly positive amount. Suppose, for contradiction, that \(t\notin R\). No positive amount of \(x\) leaves \(R\): such an arc would make its endpoint reachable. Summing the divergences of \(x\) over the vertices of \(R\) cancels all amounts on arcs internal to \(R\). The sum is the amount leaving \(R\) minus the amount entering \(R\), so it is at most zero. But \(s\in R\), \(t\notin R\), and every vertex in \(R\setminus\{s\}\) has divergence zero. Thus the same sum is the divergence at \(s\), which is \(|g|-|f|>0\), a contradiction. Hence \(t\in R\). A route of positive-\(x\) arcs from \(s\) to \(t\) is a residual route; deleting any repeated-vertex portions gives a residual path. Therefore the residual network has an \(s\)-\(t\) path. This proves the converse and the theorem. \(\square\)
Using the Characterization
The theorem is a stopping test for path augmentation: while there is a residual \(s\)-\(t\) path, the current flow is not maximum; when no such path remains, it is maximum. This conclusion does not depend on which path was chosen at earlier steps. The theorem concerns the existence of a path in the current residual network, not whether the original network contains a directed path with unused capacity on every original arc.
Worked Example: A Residual Path Increases the Flow
Let \(V=\{s,a,b,t\}\). The directed arcs and capacities are \(s\to a:3\), \(s\to b:2\), \(a\to b:1\), \(a\to t:1\), and \(b\to t:3\). Consider the flow with \(f(s,a)=1\), \(f(s,b)=1\), \(f(a,b)=0\), \(f(a,t)=1\), and \(f(b,t)=1\).
At \(a\), inflow is \(f(s,a)=1\), and outflow is \(f(a,b)+f(a,t)=0+1=1\). At \(b\), inflow is \(f(s,b)+f(a,b)=1+0=1\), and outflow is \(f(b,t)=1\). Thus conservation holds. The value is \(|f|=f(s,a)+f(s,b)=1+1=2\), and each listed flow is between zero and its capacity.
The residual capacities along \(s\to a\), \(a\to b\), and \(b\to t\) are, respectively, \(3-1=2\), \(1-0=1\), and \(3-1=2\). Thus \(s,a,b,t\) is a residual path with bottleneck \(\min\{2,1,2\}=1\). Augment by \(1\): the new flows on those arcs are \(f(s,a)=1+1=2\), \(f(a,b)=0+1=1\), and \(f(b,t)=1+1=2\); the other two flows remain \(f(s,b)=1\) and \(f(a,t)=1\).
Check: At \(a\), inflow and outflow are \(2\) and \(1+1=2\). At \(b\), they are \(1+1=2\) and \(2\). The new value is \(2+1=3\), one greater than the original value \(2\). All changed flows are within capacity: \(2\le3\), \(1\le1\), and \(2\le3\). The update is feasible and verifies the theorem's forward direction in this network.
Worked Example: No Residual Path Certifies a Maximum Flow
Let \(V=\{s,a,b,t\}\), with arcs \(s\to a:2\), \(s\to b:1\), \(a\to b:1\), \(a\to t:1\), and \(b\to t:2\), where each arc is shown with its capacity. Set the flows to \(f(s,a)=2\), \(f(s,b)=1\), \(f(a,b)=1\), \(f(a,t)=1\), and \(f(b,t)=2\).
At \(a\), inflow is \(2\) and outflow is \(1+1=2\). At \(b\), inflow is \(1+1=2\) and outflow is \(2\). Each flow equals its arc capacity, so the flow is feasible, and its value is \(2+1=3\).
Both arcs leaving \(s\) are saturated: the forward residual capacities are \(2-2=0\) on \(s\to a\) and \(1-1=0\) on \(s\to b\). There is no usable residual arc leaving \(s\), hence no residual \(s\)-\(t\) path. The theorem therefore certifies that this flow is maximum.
Check: The sum of capacities on the two arcs leaving \(s\) is \(2+1=3\). Any feasible flow has value at most \(3\), since its net flow out of \(s\) cannot exceed the total capacity \(3\) of these outgoing arcs. The displayed feasible flow has value \(3\), confirming independently that it is maximum.
Worked Example: A Reverse Residual Arc Enables Rerouting
Let \(V=\{s,a,b,t\}\), with arcs \(s\to a:1\), \(s\to b:1\), \(a\to b:1\), \(a\to t:1\), and \(b\to t:1\), where each arc is shown with its capacity. Take \(f(s,a)=1\), \(f(s,b)=0\), \(f(a,b)=1\), \(f(a,t)=0\), and \(f(b,t)=1\).
At \(a\), inflow and outflow are \(1\) and \(1+0=1\). At \(b\), they are \(0+1=1\) and \(1\). The flow is feasible and has value \(1+0=1\). In particular, it sends the unit from \(s\) through \(a\to b\to t\).
There is a residual path \(s\to b\to a\to t\). Its first arc is forward residual capacity \(1-0=1\). Its middle arc \(b\to a\) is the reverse residual arc for \(a\to b\), with capacity \(f(a,b)=1\). Its last arc is forward residual capacity \(1-0=1\). The bottleneck is \(\min\{1,1,1\}=1\).
Augmenting by \(1\) changes the flows to \(f(s,b)=1\), \(f(a,b)=0\), and \(f(a,t)=1\); \(f(s,a)=1\) and \(f(b,t)=1\) remain unchanged. The reverse residual step has cancelled the old unit on \(a\to b\). At \(a\), inflow and outflow are now \(1\) and \(0+1=1\); at \(b\), they are \(1+0=1\) and \(1\). The new value is \(f(s,a)+f(s,b)=1+1=2\), so the update is feasible and strictly improves the flow.
Check: The two arcs into \(t\) each carry \(1\) and each have capacity \(1\), so the total flow into \(t\) is \(1+1=2\). The updated flow has value \(2\), in agreement with that total and with conservation. Without the reverse arc \(b\to a\), this rerouting path would be missed.
Common Pitfalls
Ignoring reverse residual arcs. A wrong test is to look only for a path using original arcs whose forward residual capacities are positive. In the rerouting example, the proposed route \(s\to b\to a\to t\) is usable precisely because \(b\to a\) is a reverse residual arc, even though the original arc is \(a\to b\). The correction is to include both forward residual capacity \(c(e)-f(e)\) and reverse residual capacity \(f(e)\) for every original arc.
Confusing zero capacity with positive capacity. An arc with residual capacity zero is not usable in a residual path. For example, in the maximum-flow example, the forward residual capacity from \(s\) to \(a\) is \(2-2=0\), so that arc cannot start an augmenting path. The path test requires strictly positive residual capacity on every arc.
Stopping after a locally plausible flow. A flow that satisfies all capacity and conservation conditions need not be maximum. In the first example the initial flow was feasible with value \(2\), but the residual path had bottleneck \(1\), producing a feasible flow of value \(3\). Feasibility checks whether a flow is allowed; the residual-path test checks whether it can be improved.
Check Your Understanding
Use the residual capacities and the theorem to justify each conclusion.
- Why must the bottleneck on a residual path be strictly positive?
- In the first example, list the forward and reverse residual capacities for the original arc \(a\to b\) before augmentation.
- Explain why augmenting along a simple residual \(s\)-\(t\) path preserves conservation at every internal vertex.
- In the rerouting example, which original flow is decreased by using the middle residual arc, and by how much?
- Suppose a feasible flow has no residual arc leaving \(s\). What does the characterization imply about that flow?