I am reading the text "Combinatorial Optimization: Networks and Matroids" by Eugene Lawler.
Notation/Definitions:
\begin{align}
s, \quad &\text{source vertex} \\
t, \quad &\text{sink vertex} \\
f_e, \quad &\text{flow on edge }e \\
c_e, \quad &\text{capacity of edge }e \\
\text{forward edge}: \quad &\text{edge directed from }s \text{ toward }t \\
\text{backward edge}: \quad &\text{not a forward edge}
\end{align}
Lawler defines a flow augmenting path (with respect to a given flow $\{f_e\}$) to be an undirected path $P$ from $s$ to $t$ such that all forward edges in $P$ have flow which is strictly less than their capacity (i.e., $f_e < c_e$) and all backward edges in $P$ have flow which is strictly positive (i.e., $f_e > 0$). He then goes on to say,
"The problem of finding a maximum capacity flow augmenting path is evidently quite similar to the problem of finding a shortest path, or, more precisely, a path in which the minimum arc length is maximum."
My question is: What is the definition of the capacity of a flow augmenting path?
Best Answer
The capacity of a flow augmenting path is $$\min\left(\min_{\text{forward edges $e$}}(c_e-f_e),\min_{\text{backward edges $e$}}f_e\right).$$ It is the amount of flow that can be added along each edge of the path while still respecting $0 \le f_e \le c_e$.