Augmenting path

An augmenting path in a flow network is a path from the source to the sink in the residual network for some flow. It is so named because it is possible to augment (increase) the value of the flow by combining the existing flow with additional flow along the augmenting path.

Augmenting a flow

Let $f$ be a flow in the flow network $(V, s, t, c)$. Let $(V, s, t, r)$ be the residual network corresponding to $f$. Now consider an augmenting path $(s = v_0, v_1, \ldots, v_n = t)$ in the residual network. We will assume that the augmenting path is simple. Since edges must have positive capacity, the minimum residual capacity along all arcs on the augmenting path, $c_m = \min_i c(v_i, v_{i+1})$, is positive.

We define the augmented flow $f'$ as follows: $f'(u, v) = f(u, v) + c_m$ if the edge $(u, v)$ is in the augmenting path; $f'(u, v) = f(u, v) - c_m$ if the reverse edge $(v, u)$ is in the augmenting path, and, otherwise, $f'(u, v) = f(u, v)$.

Proposition: The augmented flow $f'$ is an admissible flow. Furthermore, $\sum_{v \in V} f'(s, v) = c_m + \sum_{v \in V} f(s, v)$; that is, the augmented flow's value is greater than the original flow's value by $c_m$.

Proof:

1. Capacity. If $f(u, v) \leq c(u, v)$, then clearly $f'(u, v) \leq c(u, v)$ whenever $f'(u, v) = f(u, v) - c_m$ or $f'(u, v) = f(u, v)$. We only need to check the case $f'(u, v) = f(u, v) + c_m$. In this case, $(u, v)$ is an edge in the augmenting path. By definition of $c_m$, we have that $c_m \leq r(u, v)$. Therefore $f'(u, v) \leq f(u, v) + r(u, v) = f(u, v) + c(u, v) - f(u, v) = c(u, v)$, as required.
2. Skew symmetry. Let $(u, v)$ be an edge. If $(u, v)$ is an edge in the augmenting path, then $f'(u, v) = f(u, v) + c_m = -f(v, u) + c_m = -(f(v, u) - c_m) = -f'(v, u)$. If on the other hand $(v, u)$ is in the augmenting path, then $f'(u, v) = f(u, v) - c_m = -f(v, u) - c_m = -(f(v, u) + c_m) = -f'(v, u)$. If neither is true, then $f'(u, v) = f(u, v) = -f(v, u) = -f'(v, u)$.
3. Flow conservation: Let $v$ be a vertex other than the source or sink. If $v$ is not in the augmenting path, then all flows into $v$ are unchanged, and conservation is maintained. If $v$ is in the augmenting path, then (since $v \notin \{s, t\}$) it must be preceded by a vertex $v_p$ and followed by a vertex $v_n$ in the augmenting path. Then $f'(v_p, v) = f(v_p, v) + c_m$, $f'(v_n, v) = f(v_n, v) - c_m$, and all other flows into $v$ are unchanged. Since one inward flow is incremented and another decremented by the same amount, conservation is maintained.

Finally, consider the value of the augmented flow, $\sum_{v \in V} f'(s, v)$. The source is always the first vertex in the augmenting path. Thus, $\sum_{v \in V} f'(s, v) = f'(s, v_1) + \sum_{v \in V-\{v_1\}} f'(s, v) = c_m + f(s, v_1) + \sum_{v \in V-\{v_1\}} f'(s, v) = c_m + \sum_{v \in V} f(s, v)$. $_\blacksquare$

Intuitively, augmenting the flow corresponds to "pushing additional flow" along the augmenting path using residual capacity. The augmented flow is then the overall result of pushing both the original flow and the additional flow.

Augmenting path theorem

It is now clear that a flow cannot be maximal as long as an augmenting path exists, as we can increase the flow by pushing along the augmenting path. The converse is less clear: if the flow is not maximal, then an augmenting path exists. This is the topic of this section.

Theorem (Augmenting path theorem): Let $f$ be a flow in the flow network $(V, s, t, c)$. Then $f$ is maximal if and only if there is no augmenting path in the residual network $(V, s, t, r)$.

Proof: The "only if" direction is easy. The proof of the "if" direction is based on the max-flow min-cut theorem. Since there is no augmenting path, we can form the set $S \subset V$ of vertices reachable from $s$ in the residual network. As in the max-flow min-cut theorem, $\{ (u, v) \mid u \in S, v \notin S \}$ forms an s-t cut of the weighted s-t graph corresponding to the original flow network, whose total weight equals the value of the flow $f$. Since every flow's value is less than or equal to every cut's total weight, $f$ must be maximal. $_\blacksquare$

The augmenting path theorem forms the theoretical basis of the Ford–Fulkerson method for computing a max flow.