# Maximum flow with maximum flow on specific edge

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!

• You can use linear programming to solve it. Sep 9, 2019 at 9:45

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)$$.