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.

  • 1
    $\begingroup$ 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? $\endgroup$
    – D.W.
    Dec 23 '21 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.