## Description

Q1. Determine if the following statements are true or false. If true, give

a brief explanation. If false give a counterexample. (10 points)

(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.

Q2. 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.

Prove your algorithm is correct by making an if-and-only-if claim (10

points)

Q3. 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.) (10 points)

Q4. 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: (15 points)

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?

Q5. 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. (20 points)

(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.

Q6. Given the below graph solve the below questions using scaled version of

Ford-Fulkerson. (15 points)

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

Q7:The following graph G has labeled nodes and edges between

them. Each edge is labeled with its capacity. (10 points)

(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?

Q8. 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.

Furthermore, consider if the capacities of the edges are greater than

one, and discuss whether your strategy still ensures the lowest

possible maximum flow. (20 points)