Residual Reachability as a Minimum-Cut Certificate

From a Stopped Search to a Cut

An augmenting-path procedure does more than find edge-disjoint paths. When no further augmentation is possible, the vertices reachable from the source in the residual network identify an edge cut. Its size equals the number of paths already packed, so the two objects certify each other: the paths show that no cut can be smaller, and the cut shows that no larger path packing is possible.

Throughout, \(G=(V,E)\) is a finite simple undirected graph, and \(s,t\in V\) are distinct vertices. An \(s\)-\(t\) path has no repeated vertices. An \(s\)-\(t\) edge cut is a set of edges whose deletion leaves no \(s\)-\(t\) path. We seek a largest family of pairwise edge-disjoint \(s\)-\(t\) paths and a smallest \(s\)-\(t\) edge cut. If there is no \(s\)-\(t\) path initially, the empty path family and the empty edge cut are allowed.

To describe residual reachability precisely, choose an arbitrary orientation for each edge. This orientation is bookkeeping only; the graph remains undirected. Give each edge capacity \(1\). A signed flow \(f\) assigns a number \(f_e\in[-1,1]\) to each oriented edge \(e=u\to v\): positive values send flow from \(u\) to \(v\), and negative values send it from \(v\) to \(u\). At every vertex other than \(s,t\), total inflow equals total outflow. The flow value \(|f|\) is net outflow from \(s\).

If \(f_e=0\), both directions of an unused edge are available. If \(f_e=1\), the forward residual capacity is \(0\), while the reverse residual capacity is \(2\). Sending one unit on that reverse arc cancels the existing unit of flow. More generally, augmenting by one along a residual arc increases or decreases the signed flow on its edge by one, according to the arc's direction. Starting from zero, all flows and residual capacities remain integers.

The Residual-Cut Certificate

Proof. Every augmentation uses a residual path from \(s\) to \(t\), so it increases the flow value by one and preserves flow conservation at all other vertices. The flow value is at most the number of edges incident with \(s\): each such edge can contribute at most one unit of net outflow, and edges directed into \(s\) can only reduce net outflow. Thus only finitely many unit augmentations are possible. At termination, \(t\) is not reachable from \(s\), since a residual path to \(t\) would permit another augmentation. Therefore \(s\in S\) and \(t\notin S\).

Consider any edge crossing from \(S\) to \(V\setminus S\). Its residual capacity in the outward direction must be zero; otherwise its outside endpoint would also be reachable. If the edge's chosen orientation points outward, this says \(1-f_e=0\), so \(f_e=1\). If its chosen orientation points inward, the outward residual capacity is \(1+f_e\), so \(1+f_e=0\), or \(f_e=-1\). In either case the edge carries one unit outward across the boundary. Sum net outflow over vertices in \(S\). Flow conservation cancels all contributions from edges internal to \(S\), and only \(s\) has nonzero net outflow there, because \(t\notin S\). Hence the sum is \(|f|\). Each boundary edge contributes exactly one outward unit, proving the equality.

It remains to justify the path packing and minimality claims. Because all edge flows are integral and each edge has capacity \(1\), every edge carrying nonzero flow carries one unit in one direction. If \(|f|>0\), follow edges carrying positive flow outward from \(s\). This process can reach \(t\): otherwise, let \(R\) be the vertices reachable from \(s\) using positive-flow edges. No positive-flow edge leaves \(R\), so the net flow out of \(R\) is at most zero, contradicting that its sum of vertex net outflows is \(|f|>0\). Removing repeated vertices gives a path. Subtract one unit along it and repeat; each subtraction reduces the flow value by one and never uses an edge twice in the resulting collection, since each edge initially carries at most one unit. This produces \(|f|\) edge-disjoint paths.

Finally, any \(k\) edge-disjoint \(s\)-\(t\) paths must cross every \(s\)-\(t\) edge cut in distinct edges, so every such cut has size at least \(k\). The boundary of \(S\) is itself an \(s\)-\(t\) edge cut: every path from \(s\in S\) to \(t\notin S\) must leave \(S\). Its size equals \(|f|\), which is also the size of the path packing just obtained. Thus the cut is minimum and the packing is maximum. If \(|f|=0\), the empty path packing and the zero-sized boundary satisfy the same conclusions. \(\square\)

Reading the Certificate in Examples

Common Mistake: Searching the Original Graph

Residual reachability is not ordinary reachability in \(G\). In the last example, after the first augmentation, the original graph still has the path \(s,b,x,t\). But this is not an augmenting path at that stage: the edge \(xt\) is already carrying its unit toward \(t\), so it has no outward residual capacity from \(x\) to \(t\). The residual path that does work must use \(x\to a\) to cancel the earlier use of \(ax\).

A related incorrect calculation is to take the reachable set in the original graph after the algorithm stops. The original graph is connected in the last example, so that calculation gives all of \(V\), whose boundary has size \(0\). That is not an \(s\)-\(t\) cut, since it contains \(t\). The correction is to traverse only arcs with positive residual capacity; the correct set is \(S=\{s\}\), and its boundary has size \(2\).

In applications, the certificate provides a useful stopping test. After the final augmentation, record the residual-reachable set and list its boundary edges. Verify that each boundary edge is saturated outward, count those edges, and compare that count with the number of edge-disjoint paths. Agreement proves both answers at once. If the source has no residual route to the sink before any augmentation, the same construction gives a reachable set whose boundary is empty, certifying that no \(s\)-\(t\) path exists.