I've tried looking everywhere online about the intuition behind augmenting paths in residual graphs and all I have really gotten is how to systematically solve the problem of finding max flow without any real understanding why it works.
My understanding is that the augmenting path theorem (Ford-Fulkerson, 1956) says A flow f is a max
flow if and only if there are no augmenting paths.
But why is this true? How can I intuitively see this?
I also do understand that residual graphs have edges that "send flow backwards" as a way to "undo" a possibly bad path. But in the examples I saw, a path is "undone" and then never used again, we just end up having less capacity to flow through. But I'm most likely just not entirely understanding the back edges of residual graphs.
Best Answer
Say we have an augmenting path $$ s \to a \to b \gets c \to d \to t $$ with a backward edge $b \gets c$. The logic of using it to improve the flow is that:
First, we can straightforwardly transport more flow from $s$ to $a$ to $b$.
We were previously transporting some flow from $c$ to $b$, but now that we've gotten that flow to $b$ in another way, we don't need to transport as much flow from $c$ to $b$. This frees up some flow from $c$ to send elsewhere.
Then, we can send the freed-up flow from $c$ to $d$ to $t$.
The logic in point 2 is generally the logic behind backward edges.
This explains why augmenting paths help us increase the value of the flow. By itself it doesn't prove the theorem which says that augmenting paths are essentially the only way to increase the value of the flow; if no augmenting path exists, then the flow cannot be increased.
The logic here is that if no augmenting path exists, then in the residual graph, there is no path from the source $s$ to the sink $t$. We can divide the vertices into two sets: $S$, the set of vertices reachable from $s$ in the residual graph, and $T$, the vertices not reachable from $s$. There are no edges from any $v\in S$ to $w \in T$ in the residual graph, or else we'd be able to reach $w$ from $s$, too.
This means that every arc from $S$ to $T$ in the network must be at full capacity, and every arc from $T$ to $S$ must have zero flow. This means that the net flow leaving $S$ to go to $T$ is the largest it could possibly be, and in particular the flow going from $s$ to $t$ cannot be increased.