# Find a maximum flow that also maximizes the flow over a specific edge

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.

• 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? – D.W. Sep 19 '20 at 19:53