Description
1. True or False. If true, give a brief explanation. If false give a counterexample.
(a) For a flow network, there always exists a maximum flow that doesn’t include a cycle containing positive
flow.
(b) If you have non-integer edge capacities, then you cannot have an integer max-flow value.
(c) 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.
(d) If all edge capacities are multiplied by a positive number k, then the min-cut remains unchanged
2. A tourist group needs to convert all of 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 at most Skj of their
Dollars for currency cj . (For example, a tourist with 1000 dollars might be willing to convert up to 300
of their USD for Rupees, up to 500 of their USD for Japanese Yen, and up to 400 of their USD for Euros).
Assume that all tourists give their requests to the bank at the same time. Design an algorithm that the
bank can use to determine whether all requests can be satisfied. To do this, construct and draw a network
flow graph, with appropriate source and sink nodes, and edge capacities. And Prove your algorithm is
correct by making an if-and-only-if claim (10 points)
3. You are given a collection of n points U = {u1, . . . , un} in the plane, each of which is the location of a
cell-phone user. You are also given the locations of m cell-phone towers, C = {c1, . . . , cm}. A cell-phone
user can connect to a tower if it is within distance ∆ of the tower. For the sake of fault-tolerance each
cell-phone user must be connected to at least three different towers. For each tower ci you are given the
maximum number of users, mi that can connect to this tower. Give a polynomial time algorithm, which
determines whether it is possible to assign all the cell-phone users to towers, subject to these constraints.
Prove your algorithm is correct by making an if-and-only-if claim. (You may assume you have a function
that returns the distance between any two points in O(1) time.)
4. You are given a directed graph which after a few iterations of Ford-Fulkerson has the following flow.
The labeling of edges indicate flow/capacity.
(a) Draw the corresponding residual graph.
(b) Is this a max flow? If yes, indicate why. If no, find max flow.
(c) What is the min-cut
5. USC has resumed in-person education after a one-year break, with k on-site courses available this term,
labeled c1 through ck. Additionally, there are n students, labeled s1 to sn, attending these k courses. It’s
possible for a student to attend multiple on-site courses, and each course will have a variety of students
enrolled.
(a) Each student sj wishes to enroll in a specific group pj of the k available courses, with the condition
that each must enroll in at least m courses to qualify as a full-time student (where pj is greater than or
equal to m). Furthermore, every course ci can only accommodate a maximum of qi students. The task for
the school’s administration is to verify whether every student can register as a full-time student under
these conditions. Propose an algorithm to assess this scenario. Prove your algorithm is correct by making
an if-and-only-if claim.
(b) Assuming a viable solution is found for part (a) where each student is enrolled in exactly m courses,
there arises a need for a student representative for each course from among the enrolled students. However, any single student can represent at most r (where r is less than m) courses in which they are enrolled.
Develop an algorithm to check whether it is possible to appoint such representatives, building on the solution from part (a) as a foundation. Prove your algorithm is correct by making an if-and-only-if claim.
6. Given the below graph solve the below questions using scaled version of Ford-Fulkerson.
(a) Give the ∆ and path selected at each iteration.
(b) Draw the final network graph and the residual graph.
(c) Find the maxflow and mincut.
7. The following graph G has labeled nodes and edges between them. 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?
8. You are provided with a flow network where each edge has a capacity of one. This network is represented by a directed graph G = (V, E), including a source node s and a target node t. Additionally, you are
given a positive integer k. The objective is to remove k edges to achieve the greatest possible reduction in
the maximum flow from s to t in G. Your task is to identify a subset of edges F within E, where the size
of F equals k, and removing these edges from G results in a new graph G’ = (V, E-F) where the maximum
flow from s to t is minimized. Propose a polynomial-time strategy to address this issue.
