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– Szymon Stankiewicz2019年09月09日 09:45:42 +00:00Commented Sep 9, 2019 at 9:45
1 Answer 1
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.
-
$\begingroup$ Assuming you want to solve this problem efficiently, how can Dinic's algorithm (for instance) be adjusted to find a solution? $\endgroup$Ido– Ido2020年09月19日 18:24:54 +00:00Commented Sep 19, 2020 at 18:24