CS345-Assignment 3 Soved

Ford-Fulkerson algorithm in polynomial time for integer capacity
While covering the topic on Maximum Flow in the class, we showed a graph with integer capacities on which the Ford-Fulkerson algorithm can be made to run in Θ(mcmax) time, where cmax is the maximum capacity of any edge in G. This running time is not a polynomial in the input size. The objective of this assignment problem is to slightly modify the algorithm so that it runs in polynomial time for all integer capacity graphs. In fact, the intuition underlying the modified algorithm is based on the graph that we discussed in Lecture 23.

Spend sufficient time to ponder over the slight modification in the Ford-Fulkerson algorithm. Thereafter, turn over the page.


The modification required in the Ford-Fulkerson algorithm is just the following.

In each iteration, pick the path with maximum capacity in the residual network Gf and use it to increase the flow in G during that iteration.

Spend sufficient time to show that the Ford-Fulkerson algorithm after this modification will use only O(mlog2 cmax) augmenting paths to compute the maximum flow from s to t. Hence, its time complexity is polynomial in the input size. If you don’t succeed, turn over the page.


Consider the following algorithm.

 

Algorithm 1: Poly-FF(G,s,t)

 

f ← 0;

 

1.    Fill in the blanks of algorithm Poly-FF(G,s,t) suitably. This will add to your insight into the algorithm.

2.    Show that, for any graph G, the worst case number of augmenting paths used in the algorithm described on the previous page is upper bounded by the worst case number of augmenting paths used in the algorithm Poly-FF(G,s,t). Hence, in order to show that the algorithm on the previous page uses O(mlog2 cmax) augmenting paths, it suffices to show that the algorithm Poly-FF(G,s,t) uses O(mlog2 cmax) augmenting paths.

3.    A useful hint, that you may use, is the following: The outermost While loop should run for O(log2 cmax) times only. So all that is left for you to show is that the number of iterations of the inner While loop for any specific value of variable k is O(m) only. Spend sufficient time to establish this. If you don’t succeed, please turn over the page.

4.    Note that the running time of one iteration of the inner While loop is O(m). So, if we are able to establish the validity of Step 3, the running time of the algorithm Poly-FF(G,s,t) is O(m2 log2 cmax).

Proceed along the following steps.

1.    Consider the beginning of the iteration of the outermost While loop for any value, say k0, of variable k. Prove the following lemma:

Lemma 0.1 If f is the current value of the (s,t)-flow in G, then show that f ≥ fmax − 2mk0, where fmax is the maximum (s,t)-flow in G.

2.    What is the lower bound on the amount by which the flow increases in an iteration of the inner While loop for a given value k0 of variable k ?

3.    Use (1) and (2) to provide suitable arguments to establish that the inner While loop will run for O(m) times only for any specific value of k.

If you are still now able to complete the above steps, turn over the page.


The following are the hints for the steps mentioned on the previous page.

1.    In order to prove Lemma 0.1, carefully analyse the residual network Gf. If you have fully internalized the maflow-mincut theorem discussed in the lecture, you should have no difficulty to do this task.

But if you are still now able to complete the above steps, turn over the page.

2.    The flow increases by at least k0. Give suitable arguments to support this claim.

3.    It follows from (1) that the current flow is away from the maximum flow by at most 2mk0. It follows from (2) that each iteration of the inner loop increases the flow by at least k. Hence the number of iterations of the inner While loop for any fixed value of k is O(m) only.


For Step 1 on the previous page:

Notice that there is no (s,t)-path in Gf with capacity ≥ 2k0. Now suitably define a (s,t)cut in Gf and then try to give a bound on the capacities of its forward and backward edges. Use it to derive a lower bound on the current flow in terms of the capacity of the cut. You might have to use the fact that the maximum (s,t)-flow is bounded by the capacity of any (s,t)-cut.