From Path Packings to Residual Networks
Suppose an undirected graph has two specified vertices \(s\) and \(t\), and we want to find several \(s\)-\(t\) paths that share no edges. A path already using an edge blocks that edge from being used again in the same direction, but a useful improvement may need to undo part of an existing path and redirect it. A residual network records both possibilities: unused edges can be used, while an edge already in use can be traversed backwards to cancel its current use.
Throughout, \(G=(V,E)\) is finite and simple, and \(s,t\in V\) are distinct. An \(s\)-\(t\) path is a sequence from \(s\) to \(t\) with consecutive vertices adjacent and no repeated vertices. A path packing is a set of pairwise edge-disjoint \(s\)-\(t\) paths. We consider unit capacity: each undirected edge can be used by at most one path in the packing.
The fixed orientations are bookkeeping devices; the graph itself remains undirected. A packing of \(k\) edge-disjoint paths defines a signed flow of value \(k\): on each path edge, set \(x_e=1\) or \(-1\) according to whether the path follows or opposes the fixed orientation. Because the paths share no edges, no edge receives conflicting assignments. At each internal path vertex, one unit enters and one leaves, so the divergence is zero; at the terminals, the total divergences are \(k\) and \(-k\).
Which Arcs Are Residual?
For each original edge, the residual network records directions in which its current signed flow can still be changed without exceeding the unit-capacity bounds. If its fixed orientation is \(u\) to \(v\), then increasing \(x_e\) by one corresponds to the residual arc \(u\to v\); decreasing \(x_e\) by one corresponds to \(v\to u\).
A residual arc does not mean that the original undirected edge has become directed permanently. It specifies one permitted change to the current flow. On an unused edge, either direction can be chosen. On a used edge, only the reverse direction is available, because that change cancels the existing unit rather than sending a second unit over the edge.
Worked Example: Rerouting an Existing Path
Let \(V=\{s,a,b,t\}\) and \(E=\{sa,ab,bt,sb,at\}\). Fix orientations \(s\to a\), \(a\to b\), \(b\to t\), \(s\to b\), and \(a\to t\). Begin with the one-path packing \(s,a,b,t\). Its flow values, in the stated edge order, are \(x_{sa}=1,\ x_{ab}=1,\ x_{bt}=1,\ x_{sb}=0,\ x_{at}=0\).
The used edges \(sa,ab,bt\) each have only their reverse residual arcs: \(a\to s,\ b\to a,\ t\to b\). The unused edges \(sb\) and \(at\) each have both directions available. Therefore \(s\to b\to a\to t\) is a residual \(s\)-\(t\) path: \(s\to b\) uses an unused edge, \(b\to a\) cancels the use of \(ab\), and \(a\to t\) uses another unused edge.
Augmenting along this path changes the values as follows. On \(sb\), the fixed orientation agrees with the residual arc, so \(x_{sb}:0\mapsto1\). On \(ab\), the residual arc opposes its fixed orientation, so \(x_{ab}:1\mapsto0\). On \(at\), the fixed orientation agrees, so \(x_{at}:0\mapsto1\). The other values stay \(x_{sa}=1\) and \(x_{bt}=1\). The resulting flow is represented by the paths \(s,a,t\) and \(s,b,t\), which share no edges.
Check: The new packing has two paths. Each uses two edges, so its four used edges are \(sa,at,sb,bt\); these are distinct edges of \(E\). The canceled edge \(ab\) is unused. The flow values are all in \(\{-1,0,1\}\), and the divergence at \(s\) is \(1+1=2\), while the divergence at \(t\) is \(-1-1=-2\).
Why Augmentation Works
Proof. Take a simple residual path from \(s\) to \(t\). For each edge it traverses in the fixed orientation, increase that edge's value by one; for each edge it traverses against the fixed orientation, decrease its value by one. A simple path does not repeat a vertex, so it cannot traverse the same undirected edge twice. For a forward residual arc, the current integer value satisfies \(x_e<1\); since \(x_e\in\{-1,0,1\}\), increasing it by one leaves a value in \(\{-1,0,1\}\). For a reverse residual arc, \(x_e>-1\), so decreasing it by one also leaves a value in that set. Thus all capacity bounds remain satisfied.
At each internal vertex of the path, the change brings in one unit and sends out one unit, so its divergence is unchanged. The change sends one additional unit out of \(s\) and brings one additional unit into \(t\). The new flow therefore has value \(k+1\), and every value remains an integer.
It remains to justify the assertion about paths, because a flow can contain directed cycles as well as terminal paths. Orient every nonzero-flow edge in the direction in which its unit flows. The resulting directed edges each carry one unit. For any integral flow of value \(q>0\), there is a directed \(s\)-\(t\) path among these edges: otherwise, let \(S\) be the vertices reachable from \(s\) by directed edges carrying flow. Then \(s\in S\) and \(t\notin S\). No positive-flow edge leaves \(S\), so the sum of divergences over \(S\), equal to flow leaving \(S\) minus flow entering \(S\), is at most zero. But the divergence sum is \(q\), since \(s\) contributes \(q\), \(t\notin S\), and all other vertices contribute zero. This contradicts \(q>0\). A directed walk to \(t\), if one is obtained, contains a path: deleting the section between two repeated occurrences of a vertex removes a closed part and preserves the endpoints.
Remove one unit from every edge of this directed \(s\)-\(t\) path. Its edges become unused, the remaining values still satisfy the bounds, and the remaining flow has value \(q-1\). Repeating this argument extracts \(q\) pairwise edge-disjoint \(s\)-\(t\) paths, since each extracted path's edges are removed before the next is chosen. Apply this to the augmented flow, whose value is \(k+1\). It contains a packing of \(k+1\) paths. Any flow left after those paths have been removed has value zero; it need not be zero on every edge, because it may consist of directed cycles. \(\square\)
Worked Example: A Direct Second Route
Let \(V=\{s,a,b,t\}\), \(E=\{sa,at,sb,bt\}\), and orient the edges \(s\to a\), \(a\to t\), \(s\to b\), \(b\to t\). Start with the single path \(s,a,t\), so \((x_{sa},x_{at},x_{sb},x_{bt})=(1,1,0,0)\).
The residual arcs on \(sa\) and \(at\) are \(a\to s\) and \(t\to a\), respectively. The unused edges supply both directions, including \(s\to b\) and \(b\to t\). Thus \(s,b,t\) is a residual path. Increasing the values on \(sb\) and \(bt\) gives \((1,1,1,1)\). This flow corresponds to the paths \(s,a,t\) and \(s,b,t\).
Check: The paths use edges \(\{sa,at\}\) and \(\{sb,bt\}\), whose intersection is empty. The source divergence is \(x_{sa}+x_{sb}=1+1=2\); the sink divergence is \(-x_{at}-x_{bt}=-1-1=-2\). All four edge values have absolute value \(1\).
Flows May Also Contain Cycles
The path-extraction argument is important because it does not claim that every nonzero edge of a flow belongs to an \(s\)-\(t\) path. A directed circulation is a flow around a cycle whose divergence is zero at every vertex. Such a circulation can be present alongside terminal paths. It does not change the flow value, and it does not invalidate the conclusion that the flow contains the required number of edge-disjoint terminal paths.
Worked Example: A Terminal Path and a Disjoint Circulation
Let \(V=\{s,t,a,b,c\}\) and \(E=\{st,ab,bc,ca\}\). Fix orientations \(s\to t,\ a\to b,\ b\to c,\ c\to a\). Set \(x_{st}=1\) and \(x_{ab}=x_{bc}=x_{ca}=1\). The edge \(st\) carries one unit from \(s\) to \(t\); the triangle carries one unit around \(a\to b\to c\to a\).
The divergence at \(s\) is \(1\) and at \(t\) is \(-1\). At \(a\), one unit leaves on \(ab\) and one enters on \(ca\), giving divergence \(1-1=0\); the same calculation gives zero at \(b\) and \(c\). Thus this is an integral flow of value \(1\), and all four used edges have absolute value \(1\).
The flow contains the path \(s,t\), as well as the directed cycle \(a,b,c,a\). The path alone does not account for the three nonzero triangle edges. The correct conclusion is that the flow contains one edge-disjoint \(s\)-\(t\) path; it is not correct to say that the path represents every nonzero edge of the flow.
Check: The path packing \(\{s,t\}\) has size \(1\), equal to the flow value. The triangle edges are disjoint from \(st\), and their total divergence at each triangle vertex is zero, so they contribute no additional terminal flow.
Common Pitfall: Treating a Used Edge as Still Available Forward
In the rerouting example, the edge \(ab\) already carries one unit from \(a\) to \(b\). It is therefore not valid to use \(a\to b\) as a residual arc: doing so would change \(x_{ab}=1\) to \(x_{ab}=2\), violating the unit-capacity bound. The available residual direction is \(b\to a\), which cancels that use. Conversely, on an unused edge \(sb\), both \(s\to b\) and \(b\to s\) are available.
Another error is to suppose an augmenting path simply adds a new original path while leaving every old path unchanged. The rerouting example shows why that need not be possible: the augmentation cancels \(ab\), and the resulting packing replaces the old route with two paths. What is guaranteed is a new feasible integral flow of value one greater, and hence a packing of that larger size—not that the original paths remain untouched.
Residual augmentation is the local mechanism behind algorithms for improving path packings. Its validity rests on two checks: every residual step changes an edge only within its capacity bounds, and the changes along a terminal path preserve conservation internally while increasing the value at the terminals by one. Establishing what happens when no augmenting path exists is a separate step; the augmentation argument alone makes no minimum-cut claim.
Check Your Understanding
Use the definitions and update rule above to answer each question.
- An edge has fixed orientation \(u\to v\) and current value \(x_e=-1\). Which residual direction or directions does it supply?
- For the rerouting example, list the three edge-value changes made along \(s\to b\to a\to t\), including the sign of each change.
- Explain why a simple residual \(s\)-\(t\) path cannot use both directions of the same undirected edge.
- Why does extracting a path from an integral flow and removing its edges preserve the capacity bounds?
- Give a reason that an integral flow of positive value might have nonzero edges that do not belong to any of its extracted terminal paths.