Let G = (V, E) be a flow network with source s, sink t, and suppose each edge e  E has capacity c(e) = 1

Let G = (V, E) be a flow network with source s, sink t, and suppose each edge e ? E has capacity c(e) = 1. Assume also, for convenience, that |E| = ? (V).

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?
Answers:

The running time is: O(V E) because: the running time is O(E | f*|), and | f*| = O (V) because the ?ow is bounded by the capacity of any cut, and the capacity of the cut (s, V − s) is O(V ) because there are O(V ) edges leaving s, and every edge has capacity=1.

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 your algorithm.

Answers:

Just execute one more iteration of the Ford-Fulkerson algorithm. The new edge in E adds a new edge to the residual graph, so look for an augmenting path and update the ?ow if a path is found.
The time is O(V + E) = O(E) if ?nd path with depth-?rst or breadth-?rst search.
Only 1 iteration is needed because adding the capacity-1 edge increases the capacity of the min cut by at most 1. Thus the mas ?ow (which = the min cut capacity) increases by at most 1. Since all edge capacities are 1, any augmentation increases ?ow by 1, so only 1 augmentation can be needed.

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

Let the removed edge by (u, v).
If (u, v) has no ?ow, we don't need to do anything.
If (u, v) has ?ow, the network ?ow must be updated.
There is now 1 more unit of ?ow coming into u than is going out ( and 1
more unit going out of v than is coming in). Te idea is to try to reroute this
unit of ?ow so that it goes out of u and into v via some other path. If that is
not possible, we must reduce the ?ow from s to u and from v to t by 1 unit.
So look for an augmenting path from u to v. (Note: not from s to t)
If there is such a path, augment the ?ow along that path.
If there is no such path, reduce the ?ow from s to u by augmenting the ?ow
from u to s. That is, ?nd an augmenting path u ; s and augment the ?ow
along that path. ( There de?nitely is such a path, because there is ?ow from
s to u.) Similarly augment the path from t to v.
THe time is: O(V + E) = O(E) if ?nding path with DFS or BFS.                                                                                            please see the attached file.