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

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.

• I suggest you work through some small graphs. Start with your ideas. Can you identify any patterns in which saturated edges do work, and which don't?
– D.W.
Dec 23, 2021 at 3:32

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.