Assume we are given a flow network G=(V, E) where every edge has capacity 1. I want to design an efficient algorithm to find an edge e such that removing it from G would result in a G' with a lesser max (s, t)-flow than G.
I thought of several properties that G has:
- Flow of any edge is binary; there is either flow or no flow
- Increasing flow of an edge is equivalent to reversing it on the residual graph
- Number of nonzero ingoing edges = number of nonzero outgoing edges for all intermediate nodes
- Altering any edge on a (s, t)-path removes all flow from that path
Besides running Ford-Fulkerson and choosing any edge belonging to a min (s, t)-cut, I can't think of anything else.
Using the fact that G only contains edges of capacity 1, is there a more efficient algorithm? Thanks.