From Residual Reachability to a Cut
When a flow has no augmenting path from its source to its sink, the residual network still records where additional flow might be sent or where existing flow might be cancelled. The vertices reachable from the source through positive residual capacity give a natural division of the network: the reachable vertices form the source side, and all others form the sink side. The absence of an augmenting path ensures that the sink lies on the second side.
All networks in this tutorial are finite directed networks with a specified source \(s\), a different sink \(t\), and nonnegative capacities on their arcs. A feasible flow \(f\) satisfies \(0\leq f(e)\leq c(e)\) on each original arc \(e\), and at every vertex other than \(s,t\), the total incoming flow equals the total outgoing flow. Residual moves are associated with individual original arcs, so the definition also applies if a network contains arcs in both directions between a pair of vertices.
A positive forward residual capacity means that an original arc can carry more flow. A positive reverse residual capacity means that some flow on its original arc can be cancelled. An augmenting path is an \(s\)-to-\(t\) path of positive-capacity residual moves. The search below uses both kinds of moves: looking only at original arcs with unused capacity can miss reachable vertices.
The Reachable Set and Its Boundary
Proof. The length-zero walk shows that \(s\) is reachable from itself, so \(s\in S\). If \(t\in S\), then a residual walk from \(s\) to \(t\) exists. If that walk repeats a vertex, delete the portion between two occurrences of the repeated vertex; the remaining sequence is still a residual walk from \(s\) to \(t\). Repeating this deletion gives a path, so an augmenting path exists. This contradicts the assumption. Therefore \(t\notin S\). By definition, an \(s\)-\(t\) cut is a partition into two sets with \(s\) on one side and \(t\) on the other, so \((S,V\setminus S)\) is such a cut. \(\square\)
Proof. Write \(T=V\setminus S\). Consider an original arc \(e=(u,v)\). If \(u\in S\) and \(v\in T\), then \(c(e)-f(e)\) cannot be positive: otherwise its forward residual move would reach \(v\) from \(S\), contradicting \(v\notin S\). Hence \(c(e)-f(e)=0\), or \(f(e)=c(e)\); the arc is saturated. If \(u\in T\) and \(v\in S\), then \(f(e)\) cannot be positive: otherwise the reverse residual move from \(v\) to \(u\) would reach \(u\) from \(S\), again a contradiction. Thus \(f(e)=0\). These arguments include zero-capacity arcs, for which the first equality already holds. \(\square\)
The cut capacity is the sum of the capacities of original arcs directed from \(S\) to \(T\); arcs directed from \(T\) to \(S\) are not included in that sum. The boundary property distinguishes the two directions: outgoing cut arcs are full, while incoming cut arcs have no flow on them. These facts make the reachable set more informative than an arbitrary partition separating \(s\) and \(t\).
How to Find the Reachable Set
A queue-based search finds \(S\) by starting at \(s\) and repeatedly examining positive-capacity residual moves leaving discovered vertices. Add a vertex the first time such a move reaches it. Mark vertices when they are added, so each is processed at most once. The order in which eligible moves are examined can change the search order, but not the final set.
Why the search is complete. Every added vertex is residual-reachable: it is either \(s\), or it is reached by a positive residual move from a vertex already known to be reachable. When the queue is empty, every positive residual move leaving a discovered vertex has been examined, so its head is also discovered. Now take any residual path beginning at \(s\). Starting at \(s\), apply this closure property to each successive move along the path; every vertex on the path is discovered. Thus every residual-reachable vertex is found, and the search returns exactly \(S\). \(\square\)
Worked Example: Tracing the Search and Reading the Cut
Let the directed network have \(V=\{s,a,b,c,t\}\) and arcs \(s\to a\), \(s\to b\), \(a\to b\), \(a\to t\), \(b\to t\), and \(c\to a\). The capacity and flow on these arcs, in that order, are \((5,4),(3,3),(2,1),(3,3),(4,4),(2,0)\). The flow is feasible: at \(a\), inflow \(4+0=4\) equals outflow \(1+3=4\); at \(b\), inflow \(3+1=4\) equals outflow \(4\); and at \(c\), both totals are zero.
The forward residual capacities, computed as capacity minus flow, are \(5-4=1\) on \(s\to a\), \(3-3=0\) on \(s\to b\), \(2-1=1\) on \(a\to b\), \(3-3=0\) on \(a\to t\), \(4-4=0\) on \(b\to t\), and \(2-0=2\) on \(c\to a\). The reverse residual capacities are the corresponding flows: \(4,3,1,3,4,0\) on the reverse moves \(a\to s\), \(b\to s\), \(b\to a\), \(t\to a\), \(t\to b\), and \(a\to c\), respectively.
Start with queue \([s]\) and discovered set \(\{s\}\). At each step, examine all residual moves leaving the vertex at the front of the queue, adding only previously undiscovered heads of positive-capacity moves.
| Step | Vertex processed | New vertices | Queue after processing |
|---|---|---|---|
| Start | — | — | \([s]\) |
| 1 | \(s\) | \(a\), via residual capacity \(1\) | \([a]\) |
| 2 | \(a\) | \(b\), via residual capacity \(1\) | \([b]\) |
| 3 | \(b\) | None; \(b\to a\) has capacity \(1\), but \(a\) is already discovered, and \(b\to t\) has capacity \(0\) | \([]\) |
The search ends with \(S=\{s,a,b\}\), so \(T=\{c,t\}\). There is no positive residual move from \(S\) to \(T\), and in particular \(t\notin S\). The original arcs directed from \(S\) to \(T\) are \(a\to t\) and \(b\to t\). Both are saturated: their flows are \(3\) and \(4\), equal to their capacities \(3\) and \(4\). The only original arc directed from \(T\) to \(S\) is \(c\to a\), and its flow is \(0\).
Check: the cut capacity is \(3+4=7\). The flow leaving \(s\) is \(4+3=7\), and the flow entering \(t\) is \(3+4=7\); these calculations are consistent with the boundary conditions in this example.
Reverse Residual Moves Matter
Worked Example: A Reverse Move Extends the Source Side
Let \(V=\{s,x,y,t\}\), with arcs \(s\to x\), \(s\to y\), \(y\to x\), \(x\to t\), and \(y\to t\). Give them capacity-flow pairs \((2,1),(2,2),(1,1),(2,2),(1,1)\), respectively. This is feasible: at \(x\), inflow \(1+1=2\) equals outflow \(2\); at \(y\), inflow \(2\) equals outflow \(1+1=2\). The source sends \(1+2=3\), and the sink receives \(2+1=3\).
The positive forward residual move out of \(s\) is \(s\to x\), since \(2-1=1\); \(s\to y\) has residual capacity \(2-2=0\). The arc \(y\to x\) is saturated, but it has a reverse residual move \(x\to y\) of capacity \(f(y\to x)=1\). The arcs \(x\to t\) and \(y\to t\) have forward residual capacities \(2-2=0\) and \(1-1=0\).
Starting at \(s\), the search first reaches \(x\) using \(s\to x\). From \(x\), it reaches \(y\) using the reverse residual move \(x\to y\). From \(y\), the forward move to \(t\) has capacity \(0\), and there are no other vertices to add. Thus \(S=\{s,x,y\}\), \(T=\{t\}\), and no augmenting path exists. The cut arcs are \(x\to t\) and \(y\to t\); their capacity sum is \(2+1=3\), and both are saturated.
Check: if the reverse move \(x\to y\) were omitted, the search would incorrectly return \(\{s,x\}\). That set would leave \(y\) outside even though the original arc \(y\to x\) carries flow \(1\), contrary to the boundary property for an outside-to-inside arc. Including the reverse move correctly places \(y\) in \(S\).
Reachability Is Local to the Source
Worked Example: An Unreachable Residual Component
Let \(V=\{s,a,t,p,q\}\), with arcs \(s\to a\), \(a\to t\), \(s\to t\), and \(p\to q\). Their capacity-flow pairs are \((2,1),(1,1),(1,1),(3,0)\). At \(a\), inflow and outflow are both \(1\); the source sends \(1+1=2\), and the sink receives \(1+1=2\). The arc \(p\to q\) carries zero flow, so it causes no conservation imbalance.
The residual capacity on \(s\to a\) is \(2-1=1\). The residual capacities on \(a\to t\) and \(s\to t\) are \(1-1=0\). The component arc \(p\to q\) has forward residual capacity \(3-0=3\), but no residual path from \(s\) reaches \(p\) or \(q\). The search therefore discovers \(s\), then \(a\), and stops: \(S=\{s,a\}\) and \(T=\{t,p,q\}\).
The cut arcs are \(a\to t\) and \(s\to t\). Their capacities sum to \(1+1=2\), and both flows equal their capacities. There is no original arc from \(\{t,p,q\}\) to \(\{s,a\}\) with positive flow. The positive residual capacity on \(p\to q\) does not change the cut because neither endpoint is reachable from \(s\).
Check: the residual search starts at \(s\), not at every vertex of the network. A residual component disconnected from \(s\) contributes no vertices to \(S\), even if it contains positive residual capacity.
Common Pitfalls
Using non-strict reachability. A move with residual capacity \(0\) cannot be used. In the first example, \(a\to t\) has capacity \(3-3=0\), so it does not reach \(t\). Reachability is through moves of strictly positive residual capacity.
Searching only forward along original arcs. Residual reachability includes reverse moves that cancel existing flow. The second example shows that omitting one can produce a set that fails the required boundary condition.
Confusing a cut with a list of reachable vertices. The reachable vertices are one side, \(S\); the other side is every vertex not in \(S\). To verify that this is an \(s\)-\(t\) cut, check both \(s\in S\) and \(t\notin S\). The no-augmenting-path assumption is what guarantees the second condition.
Check Your Understanding
Answer each question using positive residual capacity, and distinguish original arcs from reverse residual moves.
- Why does \(t\notin S\) follow when there is no augmenting path?
- If an original arc \(u\to v\) goes from \(S\) to \(T\), what equality must hold between its flow and capacity? Explain why.
- If an original arc \(u\to v\) goes from \(T\) to \(S\), what must its flow be? Which residual move would contradict that conclusion if the flow were positive?
- In the second example, which residual move reaches \(y\) from \(x\), and what original arc creates it?
- Why does a positive residual arc in a component disconnected from \(s\) not put either endpoint into \(S\)?