graph theory - Finding an Edge that will Decrease the Max Flow if Deleted

Question

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.

question from:https://stackoverflow.com/questions/65930354/finding-an-edge-that-will-decrease-the-max-flow-if-deleted

Answer 1

Waitting for answers