HW 8

Problem 1

The following graph G has labeled nodes and edges between it. Each edge is labeled with 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 the max-flow value?

    (c) What is the min-cut?

 Problem 2

Determine if the following statements are true or false. For each statement, briefly explain your reasoning.

    (a) In a flow network, the value of flow from S to T can be higher than the maximum number of edge disjoint paths from S to T. (Edge disjoint paths are paths that do not share any edge)

    (b) For a flow network, there always exists a maximum flow that doesn’t include a cycle containing positive flow.

    (c) If you have non-integer edge capacities, then you cannot have an integer max flow.

    (d) Suppose the maximum s-t flow of a 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 a value of at most f + 1.

    (e) If all edges are multiplied by a positive number k, then the min-cut remains un-changed.























 


Problem 3

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 is delete k edges so as to reduce the maximum s-t flow in G by as much as possible. In other words, you should find a subset of edges F ⊆ E such that |F | = k and the maximum s-t flow in the graph G′ = (V, E \ F ) is as small as possible. Give a polynomial-time algorithm to solve this problem and briefly explain its correctness.

Follow up: If the edges have more than unit capacity, will your algorithm produce the smallest possible max-flow value?










































3


Problem 4

A tourist group needs to convert their USD into various international currencies. There are n tourists t1, t2, ..., tn and m currencies c1, c2, ..., cm. Each 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 Yen, and up to 300 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 all the requests (if it is possible). To do this, construct and draw a network flow graph, with appropriate source and sink nodes, and edge capacities.

    (b) Prove your algorithm is correct by making a claim and proving it in both direc-tions.






































4


Problem 5

USC Admissions Center needs your help in planning paths for Campus tours given to prospective students or interested groups. Let USC campus be modeled as a weighted, directed graph G containing locations V connected by one-way roads E. On a busy day, let k be the number of campus tours that have to be done at the same time. It is required that the paths of campus tours do not use the same roads. Let the tour have k starting locations A = {a1, a2, ..., ak} ⊆ V . From the starting locations, the groups are taken by

    • guide on a path through G to some ending location in B = {b1, b2, ..., bk} ⊆ V . Your goal is to find a path for each group i from the starting location, ai, to any ending location bj such that no two paths share any edges, and no two groups end in the same location bj .

    (a) Design an algorithm to find k paths ai → bj that start and end at different vertices, such that they do not share any edges.

    (b) Modify your algorithm to find k paths ai → bj that start and end in different locations, such that they do not share any edges or vertices.


































5


Problem 6

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 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 the 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 the second iteration

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


6