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.
