Question

1. Say that we are given a maximum flow in the network. Then the capacity of one of the edges e is increased by 1. Give an algorithm that checks if the maximum flow has increased

2. When we increase the capacity of some edge by 5 can it be that the flow does not increase at all?

3. When we increase the capacity of an edge by 5, can the flow grow by 7?

Please write time complexity for the algorithms

Answer 1

1. Let (u,v) be the edge whose capacity has been increased by 1 unit then either this will increase the flow by 1 unit or will not increase the flow at all. Adding one to capacity of (u,v) will increase the flow value if and only if vertex u is reachable from source vertex in the residual graph and also vertex v should have path to vertex t in the residual graph.

Thus we need to check these two condition. Below is the algorithm, which perform Breadth First Search to check whether u is reachable from s by performing BFS with s as source and also whether t is reachable from v by performing BFS from v.

Algorithm(G=(V,E),(u,v)) //G is the residual graph

1. Perform BFS from vertex s.

2. If this BFS does not cover vertex u then return 0 because flow will not increase.

3. Perform BFS from vertex v

4. If this BFS does not cover vertex t then return 0 because flow will not increase.

5. Otherwise return 1 because flow will definitely increase.

So we need to perform two BFS only and hence time complexity = O(V+E)

2. Yes this can happen. If the edge whose capacity we are increasing is not the part of any min-cut then increasing its capacity will not increase any flow value at all.

3. No this cannot happen. If we increase the flow by 5 unit, then there can at most be flow increment by 5 unit.

Please comment for any clarification.