0
$\begingroup$

enter image description here

What i'v tried doing so far is to find a simple path from s to t containing e as well as some "bottle-neck edge" of maximal value (i.e. a simple path from s to t, containing e, whose minimum capacitance-edge is maximal among all such paths). After finding such path, one can modify any generic max-flow algorithm to not consider the edges in this path until the last iteration, and only then augment the flow along this path when this remains the only path from s to t in the residual network. This guarantees that the flow through e equals exactly the maximal bottle-neck value along any path from s to t containing it. Yet I counldn't prove this is an upper bound for the flow through e. How can I continue from here ? any suggestion much appreciated.

$\endgroup$
  • 4
    $\begingroup$ Please don't post an image instead of typing the text. Images won't be found by screen readers or by other people searching for a similar problem. Also, you should cite this problem: what book or website did you find it in? $\endgroup$ – Curtis F Jun 29 '19 at 21:23

Your Answer

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

Browse other questions tagged or ask your own question.