9
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ This is a standard homework exercise. $\endgroup$
    – JeffE
    Jun 16, 2013 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, 2013 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, 2016 at 16:38
  • $\begingroup$ cs.stackexchange.com/q/86801/755, cs.stackexchange.com/q/65318/755 $\endgroup$
    – D.W. ♦
    Jan 23, 2018 at 21:31

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 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, 2016 at 0:22
  • $\begingroup$ Yes, I assumed some extra information. Should I remove my answer? $\endgroup$
    – foo
    Nov 24, 2016 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, 2016 at 8:47
  • $\begingroup$ This seems to run in $O(|V|+|E|)$. Can it be done in $O(|E|)$? $\endgroup$
    – Addem
    Apr 9, 2020 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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