Question

An edge of a flow network is called critical if decreasing the capacity of this edge results in a decrease in the maximum flow. On input a flow network G, you ran Ford-Fulkerson and computed a maximum flow f.

i. Give an efficient algorithm that finds a critical edge in G.
ii. Give an efficient algorithm that finds every critical edge in G.

Answer 1

1. Begin
2. find the residual graph of the graph G(V,E) using ford Fulkerson
3. For each edge u, v in the residual graph such that u, v is not in the residual graph and also not in G
4. Apply DFS to see if u has no path to v
5. then return edge (u,v)
6. else
7. nothing
8. end

Explanation: