find edges such that if decreased by one unit, the max flow decreases as well

Question

We are given a flow network $G = (V,E,c)$, where $c$ is the capacity function as well as a maximum flow $f_m: E\rightarrow \mathbb R$ from $s$ to $t$. The goal is to find edges such that if decreased by one unit, the value of any max flow decreases as well. The time complexity should be $O(VE)$.

I found this question in my algorithm book.

My attempt: I thought all saturated edges could satisfy this condition. Then I found some counterexamples.

Answer 1

Copied from StackOverflow:

Each arc u-->v belongs to some s--t min cut if and only if

1. there is no residual path from u to t,
2. there is no residual path from s to v, and
3. there is no residual path from u to v.

To prove the if direction, consider the cut consisting of vertices reachable from s or u by a residual path, which is an s--t cut by (1), has zero residual capacity and hence is an s--t min cut by construction, and contains u-->v by (2) and (3).

To prove the only if direction, we can use an s--t min cut that contains u-->v to show that, for every path from u to t, from s to v, or from u to v, some arc in the path is non-residual.

This gets you to O(n m) time fairly easily. Maybe that's good enough -- if it isn't, there is a literature on answering offline reachability queries that might be useful.