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!