CSCI 570  - HW 8

CSCI 570  - HW 8
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?
S B D
A C
E
T
1
3 5
4
3
2
3
2
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 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)
5. (20 pts) 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. 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 FordFulkerson 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