# Effect of increasing the capacity of an edge in a flow network with known max flow

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?

• This is a standard homework exercise. – JeffE Jun 16 '13 at 17:19
• I would argue that this question, as it stands, is under-specified. Ford-Fulkerson is an efficient algorithm, so simply rerun it and compare to $|f|$. – Pål GD Jun 17 '13 at 23:58
• Do you mean that you are given the flow (the amount sent on all edges) or only the value of the flow (the total amount that can be sent from source to sink)? Also, what's the source of this exercise? It's considered polite to [reference the source]()cs.stackexchange.com/help/referencing of material written by others that you are using in your question. – D.W. Dec 24 '16 at 16:38
• – D.W. Jan 23 '18 at 21:31

I am assuming that you are given the flow on each edge which corresponds to the maximum flow for the graph $G$. So $f_e$ is the flow on edge $e$.
Now given this information, capacity of an edge $e$ is increased by 1. Therefore, the mincut value can increase by at most 1 implying that the maxflow can increase by at most 1.
Thus, find the residual graph and check if there is an augmenting path $P$ from $s$ to $t$. If such a $P$ exists, then increase your maxflow by augmenting this path, otherwise the current flow is still the maximum.
• This seems to run in $O(|V|+|E|)$. Can it be done in $O(|E|)$? – Addem Apr 9 '20 at 19:46