HW 8 Solution

Graded

    1. (10 pts) The following graph G has labeled nodes and edges between it. Each edge is labeled with the its capacity.

        (a) Draw the final residual graph Gf using the Ford-Fulkerson algorithm corresponding to the max flow. Please do NOT show all intermediate steps.

        (b) What is max-flow value?

        (c) What is the min-cut?

3    2

A  C  T

3
5
3

1    4    2

S  B  D  E


    2. (15 pts) The following statements may or may not be correct. For each statement, if it is correct, provide short description. If it is incorrect, provide a counter-example to show that it is incorrect.

        (a) In the capacity-scaling algorithm, an edge e can be present in the residual graph Gf (D) in at most one D-scaling phase.

        (b) Suppose the maximum (s,t)-flow of some graph has value f. Now we increase the capacity of every edge by 1. Then the maximum (s,t)-flow in this modified graph will have value at most f + 1.

        (c) If all edges are multiplied by a positive number ’k’ then the min-cut remains unchanged.

    3. (15 pts) You are given a flow network with unit-capacity edges: it consists of a directed graph G = (V, E) with source s and sink t, and ue = 1 for every edge e. You are also given a positive integer parameter k. The goal


1





is delete k edges so as to reduce the maximum s − t flow in G by as much as possible. Give a polynomial-time algorithm to solve this problem. In other words, you should find a set of edges F ⊆ E so that |F | = k and the maximum st flow in the graph G’ = (V, E-F ) is as small as possible. Give a polynomial-time algorithm to solve this problem.

Follow up: If the edges have more than unit capacity, will your algorithm guarantee to have minimum possible max-flow?

    4. (40 pts) USC students return to in person classes after a year long interval. There are k in-person classes happening this semester, c1, c2, ..., ck. Also there are n students, s1, s2, ..., sn attending these k classes. A student can be enrolled in more than one in-person class and each in-person class consists of several students.

        (a) (20 pts) Each student sj wants to sign up for a subset pj of the k classes. Also, a student needs to sign up for at least m classes to be considered as a full time student. (Given: pj ≥ m) Each class ci has capacity for at most qi students. We as school administration want to find out if this is possible. Design an algorithm to determine whether or not all students can be enrolled as full time students. Prove the correctness of the algorithm.

        (b) (20 pts) If there exists a feasible solution to part (a) and all students register in exactly m classes, the student body needs a student representa-tive from each class. But a given student cannot be a class representative for more than r (where r < m) classes which s/he is enrolled in. Design an algorithm to determine whether or not such a selection exists. Prove the correctness of the algorithm. (Hint: Use part (a) solution as starting point)

    5. (20 pts) A tourist group needs to convert their USD into various interna-tional currencies. There are n tourists t1, t2, ..., tn and m currencies c1, c2, ..., cm. Tourist tk has Fk Dollars to convert. For each currency cj , the bank can convert at most Bj Dollars to cj . tourist tk is willing to trade as much as Skj of his Dollars for currency cj .(For example, a tourist with 1000 dollars might be willing to convert up to 200 of his USD for Rupees, up to 500 of his USD for Japanese’s Yen, and up to 200 of his USD for Euros). Assume that all tourists give their requests to the bank at the same time.

            (a) Design an algorithm that the bank can use to satisfy the requests (if it is possible). Also, construct and draw the network flow graph, with source, sink appropriate nodes, and edge capacities.

            (b) Prove your algorithm, by making a claim and proving it in both directions.

    6. (20 pts) Perform two iterations (i.e. two augmentation steps) of the scaled version of the Ford- Fulkerson algorithm on the flow network given below. You need to show the value of ∆ and the augmentation path for each

2





iteration, and the flow f and Gf (∆) after each iteration. (Note: iterations may or may not belong to the same scaling phase)


















    (a) i. Give the value of ∆ and the augmentation path

        ii. Show the flow after the first iteration
        iii. Show the Gf (∆) after first iteration

    (b) i. Give the value of ∆ and the augmentation path

        ii. Show the flow after the second iteration
        iii. Show the Gf (∆) after second iteration

    (c) Can the choice of augmentation paths in the scaled version of Ford-Fulkerson affect the number of iterations? Explain why


Ungraded

    7. A vertex cover of an undirected graph G = (V, E) is a subset of the vertices A ⊆ V such that for every edge e ∈ E, at least one of its incident vertices is in A (that is every edge has at least one of its ends in A). Design an algorithm that takes a bipartite graph G′ and a positive integer k, and decides if G′ has a vertex cover of size at most k.













3