Residual graph
In graph theory, a residual graph, also called a residual network, represents the additional changes that remain feasible for a flow in a flow network. Each residual edge records how much flow can still be sent in one direction or canceled in the opposite direction. The construction converts the local constraints of a current flow into an auxiliary directed graph, allowing questions about further augmentation, optimality, and minimum cuts to be expressed as reachability problems.
Residual graphs are central to the maximum-flow problem. They also occur in minimum-cost flow, bipartite matching, circulation problems, and algorithms based on blocking flows or preflows. Although the residual graph has the same vertex set as the original network, its edge set and capacities depend on the current flow and therefore change during an algorithm.
Definition
Let
[ G=(V,E) ]
be a directed network with source (s), sink (t), and nonnegative capacity function
[ c:E\rightarrow \mathbb{R}_{\geq 0}. ]
A feasible flow (f) assigns a value (f(u,v)) to every edge ((u,v)\in E). It satisfies the capacity constraints
[ 0\leq f(u,v)\leq c(u,v) ]
and obeys flow conservation at every vertex other than (s) and (t).
For an original edge ((u,v)), the forward residual capacity is
[ c_f(u,v)=c(u,v)-f(u,v). ]
This quantity measures the additional flow that can pass through the edge without violating its capacity. The corresponding reverse residual capacity is
[ c_f(v,u)=f(u,v), ]
which measures how much of the existing flow can be canceled. A residual edge is present precisely when its residual capacity is positive.
Under an antisymmetric formulation, capacities of absent edges are treated as zero and the flow satisfies
[ f(u,v)=-f(v,u). ]
The residual-capacity expression then becomes
[ c_f(u,v)=c(u,v)-f(u,v). ]
This notation incorporates forward augmentation and reverse cancellation into a single formula. When the original network contains antiparallel or parallel edges, edge identities must be retained or their residual capacities must be aggregated consistently; otherwise an original edge can be confused with the reverse residual edge generated by another edge.
The residual graph associated with (f) is therefore
[ G_f=(V,E_f), ]
where
[ E_f={(u,v)\mid c_f(u,v)>0}. ]
It is an auxiliary graph rather than a subgraph of (G), because it can contain reverse edges that did not occur in the original network.
Augmentation
An augmenting path is a directed path from (s) to (t) in (G_f). Its residual capacity, often called its bottleneck capacity, is the minimum residual capacity among its edges:
[ \Delta(P)=\min_{(u,v)\in P}c_f(u,v). ]
Augmenting the flow by (\Delta(P)) increases flow on forward residual edges and decreases flow on residual edges that represent cancellation. The value of the total flow increases by (\Delta(P)), while feasibility is preserved.
For example, suppose an original edge has capacity (10) and currently carries flow (6). Its forward residual capacity is (4), whereas its reverse residual capacity is (6). A later augmenting path can therefore add no more than (4) units through the edge in its original direction, or it can cancel as many as (6) units by traversing the reverse residual edge. This reversibility permits an algorithm to revise an earlier routing choice without discarding the rest of the current flow.
Augmentation changes only residual capacities associated with the traversed edges. If (\Delta) units are sent along a residual edge ((u,v)), then its residual capacity decreases by (\Delta), while the capacity of the opposite residual edge increases by the same amount. This paired update preserves the correspondence between the residual graph and the revised feasible flow.
Relation to maximum flow and minimum cut
The absence of an (s)-to-(t) path in (G_f) characterizes a maximum flow. If such a path existed, its positive bottleneck capacity would permit a further increase in flow value. Conversely, when no augmenting path exists, let (S) denote the vertices reachable from (s) in the residual graph and let (T=V\setminus S). The sink belongs to (T).
Every original edge from (S) to (T) is saturated, because positive unused capacity would create a residual edge crossing from (S) to (T). Every original edge from (T) to (S) carries zero flow, because positive flow would create a reverse residual edge from (S) to (T). Consequently, the current flow value equals the capacity of the cut ((S,T)).
This argument forms the constructive core of the max-flow min-cut theorem:
[ \max_f |f|=\min_{(S,T)} c(S,T). ]
The residual graph thus serves two roles. During computation it encodes permitted changes to a nonoptimal flow, while at termination its reachability structure provides a minimum-cut certificate.
Layered residual networks
A layered residual network is derived from shortest-path distances in the residual graph. A breadth-first search from (s) assigns each reachable vertex a level, and only residual edges satisfying
[ \operatorname{level}(v)=\operatorname{level}(u)+1 ]
are retained. The resulting directed acyclic structure is commonly called a level graph.
The 1970 layered-network formulation developed by Yefim Dinitz and You Watanabe connected residual distance with the computation of a blocking flow. Their analysis established that after a blocking flow saturates or otherwise blocks every source-to-sink path in the current level graph, the residual distance from (s) to (t) strictly increases. Repeated phases therefore terminate after fewer than (|V|) level increases.
This structure underlies Dinic's algorithm, whose general running-time bound is
[ O(|V|^2|E|). ]
The same residual interpretation supports stronger bounds on restricted network classes, because unit capacities or constrained incidence patterns limit the number and arrangement of blocking-flow phases.
Algorithmic development
Lester R. Ford Jr. and Delbert R. Fulkerson placed residual capacities at the center of the augmenting-path method introduced in the 1950s. In the Ford–Fulkerson algorithm, successive source-to-sink paths are selected from the current residual graph until no such path remains. With integer capacities, every augmentation increases the flow value by at least one, giving a running-time bound proportional to the product of the number of edges and the maximum-flow value.
The path-selection rule affects both complexity and termination behavior. Jack Edmonds and Richard Karp analyzed the rule that always chooses a residual path containing the fewest edges. Their Edmonds–Karp algorithm runs in
[ O(|V||E|^2) ]
time, independently of the numerical magnitude of the capacities. Its analysis depends on the monotonic increase of residual shortest-path distances and on a bound for the number of times an edge can become critical.
Augmenting-path algorithms are not the only methods that maintain residual graphs. The push–relabel algorithm stores a preflow that may temporarily violate conservation at intermediate vertices. Residual edges still determine permissible transfers, while a height function restricts pushes to residual directions compatible with the algorithm's local ordering. At termination, the preflow becomes a feasible maximum flow, and residual reachability again determines a minimum cut.
Integrality and termination
If every capacity is an integer, each residual capacity remains integral after integral augmentations. An augmenting-path method that always sends the full bottleneck amount therefore constructs an integral maximum flow. This is the residual-network form of the integral flow theorem, which is important in reductions from matching and assignment problems.
For arbitrary irrational capacities, unrestricted path selection in the Ford–Fulkerson method can generate an infinite sequence of augmentations whose flow values converge without reaching the maximum. The residual graph remains well defined throughout such a sequence, but its existence alone does not impose a finite bound on the number of updates. Algorithms with combinatorial path-selection rules avoid this dependence on capacity arithmetic.
Minimum-cost residual graphs
In a minimum-cost flow problem, every original edge additionally has a cost per unit of flow. The forward residual edge retains the original cost, while the reverse residual edge receives its negation. Sending flow through a reverse edge then represents canceling earlier flow and recovering the associated cost.
A directed residual cycle with negative total cost identifies a feasible circulation adjustment that lowers the objective value without changing the net flow between the source and sink. The absence of an applicable negative-cost residual cycle is therefore an optimality condition for a feasible flow of fixed value. Equivalent formulations use reduced cost and vertex potentials, which transform residual edge costs while preserving the costs of directed cycles.
Successive-shortest-path methods also operate on costed residual graphs. Each augmentation changes capacities and may introduce reverse edges with negative costs, so potentials are maintained to permit shortest-path computations with nonnegative reduced costs. The underlying capacity interpretation remains identical to that of an ordinary residual graph.
Structural interpretation
A residual graph describes the local difference between a current feasible solution and neighboring feasible solutions. Forward edges represent unused capacity, whereas reverse edges encode decisions that can be undone. A directed residual cycle corresponds to a circulation adjustment that preserves the value of the flow, while a residual path from (s) to (t) corresponds to an adjustment that increases it.
The construction also explains why greedy routing without reverse edges is insufficient for general maximum-flow computation. A locally chosen path can consume capacity required by a later routing, but the generated reverse edges permit the earlier choice to be partially or completely canceled. Residual reachability consequently records not only unused physical capacity but also the combinatorial flexibility created by the current assignment.