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?

  • $\begingroup$ This is a standard homework exercise. $\endgroup$ – JeffE Jun 16 '13 at 17:19
  • $\begingroup$ 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|$. $\endgroup$ – Pål GD Jun 17 '13 at 23:58
  • $\begingroup$ 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. $\endgroup$ – D.W. Dec 24 '16 at 16:38
  • $\begingroup$ cs.stackexchange.com/q/86801/755, cs.stackexchange.com/q/65318/755 $\endgroup$ – 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$.

I am also assuming that all the capacities and flows values are integral.

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.

| cite | improve this answer | |
  • 2
    $\begingroup$ The question just says that you're given the size of the maximum flow, not the flows on each edge. $\endgroup$ – David Richerby Nov 24 '16 at 0:22
  • $\begingroup$ Yes, I assumed some extra information. Should I remove my answer? $\endgroup$ – foo Nov 24 '16 at 0:58
  • $\begingroup$ I don't think you need to delete it but it's probably best to stick to questions you can answer without extra assumptions. Thanks for contributing! $\endgroup$ – David Richerby Nov 24 '16 at 8:47
  • $\begingroup$ This seems to run in $O(|V|+|E|)$. Can it be done in $O(|E|)$? $\endgroup$ – Addem Apr 9 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.