Let $G=(V,E,c,s,t)$ be a flow-network, where $s$ is the source, $t$ is the target, and $c:E\mapsto [0,\infty)$ defines the capacity of every edge in the network. Let $e=(u,v)$ be an edge in the network. Describe an efficient algorithm to find a valid maximum flow $f$, such that $f(e)$ has a maximal value. (That is, if $f'$ is also a maximum flow, then $f'(e)\leq f(e)$).

I found someone asking the same question here, but the solution itself did not focus on achieving a good runtime complexity. The solution suggested augmenting paths that go through $(u,v)$ before any other paths, which is very intuitive and reasonable. However, I could not think of an efficient way of doing so. Ideally, I would want to adjust Dinic's algorithm so that paths from $s$ to $t$ that go through $(u,v)$ will be discovered first, but it is not simple.

I was also thinking of computing a maximum flow $f$ using Dinic's algorithm, and then adjusting it somehow so that $f(e)$ increases while $|f|$ stays unchanged. However, I could not think of an efficient way to do so.

I'd appreciate any help, thanks.

  • $\begingroup$ What counts as efficient for you? What is the best running time you already know how to achieve? Can you credit the original source where you encountered this problem? $\endgroup$ – D.W. Sep 19 '20 at 19:53

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.