I need your help with an exercise on Ford-Fulkerson.
Suppose you are given a flow network with capacities $(G,s,t)$ and you are also given the max flow $|f|$ in advance.
Now suppose you are given an arc $e$ in $G$ and suppose this arc's capacity is increased by one.
Give an efficent algorithm which returns true iff the increase of the capacity of the arc $e$ will allow an increase in the max flow.
I suppose we shouldn't run Ford-Fulkerson again but somehow use the given $|f|$… Any ideas how?