Let G=(V,E) be a flow network with source s and sink t, and each edge e ∈ E has capacity c(e)=1. Let n = |V| and m = |E|, and assume that m = Ω(n).

a) Suppose we implement the Ford-Fulkerson maximum-flow algorithm by using depth-first search to find augmenting paths in the residual graph. What is the worst-case running time of this algorithm on G?

b) Suppose a maximum flow for G has been computed and a new edge with unit capacity is added to E. Describe how the maximum flow can be efficiently updated. (Note: It is not the value of the flow that must be updated, but the flow itself.) Analyze the time complexity of your algorithm.

c) Suppose a maximum flow for G has been computed, but an edge is now removed from E. Describe how the maximum flow can be efficiently updated. Analyze the time complexity of your algorithm.