Question

Remarks: In all algorithm, always prove why they work. ALWAYS, analyze the com- plexity of your algorithms. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. In all data structures, try to minimize as much as possible the running time of any operation. . Question 4: 1. Say that we are given a mazimum flow in the network. Then the capacity of one of the edges e is increased by 1. Give an algorithm that checks if the maximunm 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 explain

Answer 1

1. This can be solved in O(m + n) running time,

• We know that incrementing the capacity of e by 1 will result in increasing the max flow at most 1.
• Starting with the current max flow f, you only need to find an augmenting path in the residual graph one more time, which costs O(m+n) time.
• As each augmentation increments the flow value by at least 1,  it is guaranteed after the augmentation the flow achieved is maximum.

2. The solution which I proposed for Q1 will help only for incrementing and for +5 I think yes there is a possibility that the max flow won't change.