CSCI 570 HW 8

Description

Graded

1. (15 pts) You are given the following graph G. Each edge is labeled with the capacity of that edge.

A	3
	C
3	2
S	5
	T
1	3

4 2

B D E

1. 1. 1. Draw the residual graph G_f using the Ford-Fulkerson algorithm cor-responding to the max ow. You do not need to show all intermediate steps.

1. 1. 2. Find the max- ow value and a min-cut.

2. (40 pts) USC students return to in person classes after a year long interval. There are k in-person classes happening this semester, c₁, c₂, …, c_k. Also there are n students, s₁, s₂, …, s_n 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.

2. 1. Each student s_j wants to sign up for a subset p_j 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: p_j m) Each class c_i has capacity for at most q_i students. We as school administration want to nd 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.

2. 2. If there exists a feasible solution to part (a) and all students register in exactly m classes, the student body needs a student representative 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)

3. (12 pts) The following statements may or may not be correct. For each statement, if it is correct, provide a short proof of correctness. If it is incorrect, provide a counter-example to show that it is incorrect.

3. 1. If each directed edge in a network is replaced with two directed edges in opposite directions with the same capacity and connect-ing the same vertices, then the value of the maximum ow remains unchanged.

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

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

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

3. (13 pts) You are given a ow network with unit-capacity edges: it consists of a directed graph G = (V, E) with source s and sink t, and u_e = 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 ow in G by as much as possible. Give a polynomial-time algorithm to solve this problem. In other words, you should nd a set of edges F E so that jF j = k and the maximum st ow in the graph G’ = (V, E-F) is as small as possible. Give a polynomial-time algorithm to solve this problem. What happens when the edges don’t have unit capacity?

Ungraded

5. A tourist group needs to convert their USD into various international currencies. There are n tourists t₁, t₂, …, t_n and m currencies c₁, c₂, …, c_m. Tourist t_k has F_k Dollars to convert. For each currency c_j , the bank can convert at most B_j Dollars to c_j . Tourist t_k is willing to trade as much as S_kj of his Dollars for currency c_j .(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). Assuming that all tourists give their requests to the bank at the same time, design an algorithm that the bank can use to satisfy the requests (if it is possible).

6. Trip Trillionaire is planning to give potential buyers private showings of his estate, which can be modeled as a weighted, directed graph G containing locations V connected by one-way roads E. To save time, he decides to do k of these showings at the same time, but because they were supposed to be private, he doesn’t want any of his clients to see each other as they are being driven through the estate.

Trip has k grand entrances to his estate, A = fa₁; a₂; :::; a_kg V . He wants to take each of his buyers on a path through G from their starting location a_i to some ending location in B = fb₁; b₂; :::; b_kg V , where there are spectacular views of his private mountain range.

Because of your prowess with algorithms, he hires you to help him plan his buyers’ visits. His goal is if there exists a path for each buyer i from the entrance they take, a_i, to any ending location b_j such that no two paths share neither any edges nor any of the locations, and no two buyers end in the same location b_j . Prove the correctness of the algorithm.

6. A vertex cover of an undirected graph G = (V; E) is a subset of the vertices A V such that for every edge e 2 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