Description

Assignment 3
Most Important guidelines
• Refrain from collaborating with the students of other groups. If any evidence is found that confirms copying, the penalty will be very harsh. Refer to the website at the link: https://cse.iitk.ac.in/pages/AntiCheatingPolicy.html regarding the departmental policy on cheating.
General guidelines
2. You are strongly discouraged to submit the scanned copy of a handwritten solution. Instead, you should prepare your answer using any text processing software (LaTex, Microsoft word, …). The final submission should be a single pdf file.
5. Naming the file:
The submission file has to be given a name that reflects the information about the assignment number, and the roll numbers of the 2 students of the group. For example, you should name the file as Assign i Rollnumber1 Rollnumber2.pdf if you are submitting the solution for the ith assignment.
6. Each student of a group has to upload the submission file separately.
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.
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.