Why if we don't use residual graph in Ford-Fulkerson to finding
maximum flow give no any approximation of optimal solution?
With such a modification our algorithm do find a augmenting path and increase flow,continue until we have no augmenting path,I read many papers but I can't prove that without residual graph we have no any approximation of optimal solution.As the result suppose $F^*$ be optimal maximum flow,i want prove that this strategy give us $\alpha F^*$ such that $\alpha$ be a number in $0<\alpha\leq 1$.Any hint will be constructive.
Best Answer
The issue is making the "wrong" choices, in those cases the residual graph corrects them.
To understand the issue, consider the digraph with vertices $s,t,a,b$ and arcs $\overrightarrow{sa}, \overrightarrow{sb}, \overrightarrow{ab}, \overrightarrow{ta}, \overrightarrow{tb}$ of capacity $1$ each.
This graph has an obvious flow of value $2$ namely $1$ on the route $s \to a \to t$ and $1$ on the route $s \to b \to t$.
But, and here is the issue, what if you start by setting a flow of $1$ on the route $s \to a \to b \to t$. Try to increase it, and you will see that, without using the residual graph (or undoing some of the choices) you cannot.
This can be easily extrended the following way: add vertices $c,t'$ and arcs $\overrightarrow{sc}, \overrightarrow{tc}, \overrightarrow{ct'}$ of capacity $1$ and $\overrightarrow{tt'}$ of capacity $2$. Then, this netweork has a flow of 3, but the flow $s \to a \to b \to t \to c \to t'$ of value $1$ cannot be increased. And the idea of this step can be extended inductively, to create a network which admits a flow of value $n \in \mathbb N$, but which also has a flow of value 1 which cannot be increased (unless we use the residual graph/undo some choices).