I am trying to solve the following problem:

We're given a network flow $(V,E,c,s,t)$ and an edge $(u,v)$. We have to provide an algorithm that computes the maximum flow which has maximum flow on $(u,v)$ also.

The idea that I had was, computing max flow and on the residual graph trying to compute a cycle that starts from $s$ and passes through the edge $(u,v)$ and trying to increase $(u,v)$'s flow while decreasing the flow from other edges. In other words, trying to maximize the flow of $(u,v)$ while preserving the maximum flow value. But I feel like there's a simpler way.

Can someone point me in the right direction? Is my thinking correct? If not how should I approach the problem?

Any help is appreciated! Thanks!

  • $\begingroup$ You can use linear programming to solve it. $\endgroup$ – Szymon Stankiewicz Sep 9 '19 at 9:45

I would do it kind of the other way around as you suggested.

First compute a flow that saturates $(u,v)$. This can be done with the Ford--Fulkerson algorithm. Look only for augmenting paths which contain $(u,v)$ and augment the flow until the edge is saturated.

In the second step you augment further, but avoid the edge $(u,v)$ when searching for augmenting paths in the residual network. There is no reason to desaturate $(u,v)$. If we desaturate the edge with one path and saturate it with another we can get to the same flow by augmenting with the "product" path which avoids $(u,v)$.

This is not a proof but should guide you in a possible direction how to solve this.

| cite | improve this answer | |
  • $\begingroup$ Assuming you want to solve this problem efficiently, how can Dinic's algorithm (for instance) be adjusted to find a solution? $\endgroup$ – Ido Sep 19 at 18:24

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.