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.
