CSCI-570 Homework 4
April 6, 2020
1 Compute Max-Flow And Min-Cut
Solution: Figure 1 has max-flow 7. One feasible flow is S → A → C → T withflow2,S→A→B→C→T withflow1,S→B→D→T withflow 3 and S → B → C → T with flow 1. All min-cuts are {S}||{A,B,C,D,T}, {S,A,B,D}||{C,T}. Figure 2 has max-flow 7. A feasible flow is S → A → T withflow3,S→B→T withflow3andS→B→A→T withflow1. All min-cuts are {S, B}||{A, T }, {S}||{A, B, T }.
A2C A
3635 4
S1 TS11T 12
4343 B3D B
Rubric: Each subproblem has 5 points. 2 points for correct max-flow value, 1 point for any feasible max flow and 2 points for the two min cuts.
2 Escape From the Building
In this problem, we need to decide whether there is a feasible plan for all the persons in a building to escape when they meet some emergency issues. More specifically, a building is described as an n by n grid and the position of p persons are represented as the integer points (x1, y1), . . . , (xp, yp) in the building. Note that to ensure safety, we don’t allow any intersection between the paths of any two person. Therefore, your task is to decide whether there exist p vertex-disjoint paths from their starting points to any p different points on
1
the boundary of the grid. Give an algorithm polynomial in n and prove the
correctness of it.
Solution: We construct the network as follows. First, we split each point
(i, j) in the grid into two points (iin, jin) and (iout, jout) and add an edge with
capacity 1 from (iin, jin) to (iout, jout). In addition, for all (iout, jout), we add
directed edges to its adjacent in-node, namely (i + 1in, jin), (iin, j + 1in), (i −
1in, jin) and (iin, j − 1in) if they are well defined already. Then, We add a
source node S and add an directed edge from S to each start in-node (xin,yin) ii
with capacity 1, i ∈ [p] and finally, we add a sink node T and connect all the boundary out-node (iout,jout) to it with a directed edge of capacity 1. Our algorithm is to first compute an integer max-flow of this graph by using Edmund- Karp algorithm. According to our construction, the value of the max-flow is no more than p.
Claim: There exist p disjoint paths if and only if the above network has a max-flow of value p.
Proof: If there exists a max-flow of value p, we can construct p disjoint
paths according this flow. Specifically, for each (xi,yi), there must be one unit
flow from S to (xin, yin) the finally it will reach the sink, which means it reaches ii
one of the boundary point. This one unit flow therefore indicates a path from (xi,yi) to one of the boundary point. Also, these paths will never intersect. If so, there would be two units coming into one in-node. As the corresponding out-node is of capacity 1, it is not feasible.
On the other hand, if the value of the max-flow is not p, we claim that there
does not exist such p disjoint paths because if there exists p disjoint paths, we
can construct a flow of value p by following these paths. Concretely, for a path
(xi,yi) → (xi + 1,yi) → ··· → (x∗,y∗) (The last one is the boundary point),
we have a one unit flow S → (xin,xout) → (xout,yout) → (x + 1in,yin) → iiiiii
(xout,yout) → ··· → (x∗in,y∗out). for each i ∈ [p]. This is a feasible flow as ii
the p paths are disjoint. Therefore, we show the correctness of our algorithm and the runtime is polynomial in n as the complexity of generating graph and translating the solution and Edmond Karp algorithm are all polynomial in n.
Rubric: 5 points for giving correct directed graph with capacity. 4 points for the correct claim. 3 points for the proof for each direction. (If direction and Only-if direction) (Running FF here is correct as it is polynomial time in this case.)
3 Install Software to Your New Computer
Suppose that you have just bought a new computer and you want to install soft- ware on that. Specifically, two companies, which you can think of like Microsoft and Apple, are trying to sell their own copy of n different products, like Opera- tion System. Spread Sheet, Web Browser. For each product i, i ∈ {1, 2, . . . , n}, we have
• the price pi ≥ 0 that Microsoft charges and the price p′i ≥ 0 that Apple charges.
2
• the quality qi ≥ 0 of Microsoft version and the quality qi′ ≥ 0 of Apple version.
For example, Apple may provide a better Web Browser Safari, but Microsoft a better Word Processor. You want to assemble your favorite computer by installing exactly one copy of each of the n products, e.g. you want to buy one operating system, one Web Browser, one Word Processor, etc. However, you don’t want to spend too much money on that. Therefore, your goal is to maximize the quality minus total price.
However, as you may know, the products of different companies may not be compatible. More concretely, for each product pair (i, j), we will suffer a penalty τij ≥ 0 if we install product i of Microsoft and product j of Apple. Note that τij may not be equal to τji just because Apple’s Safari does not work well on Microsoft Windows doesn’t mean that Microsoft’s Edge does not work well in Mac-OS. We assume that products are always compatible internally, which means that there is no penalty for installing two products from the same company. All pairwise penalties will be subtracted from the total quality of the system.
Your task is then to give a polynomial-time algorithm for computing which product i to purchase from which of the two companies (Apple and Microsoft) for all i ∈ {1,2,…,n}, to maximize the total system quality (including the penalties) minus the total price. Prove the correctness of your algorithm. (Hint: You may model this problem as a min-cut problem by constructing your graph appropriately.)
Solution: In this problem, we actually need to separate the objects into two parts A (Microsoft) and B (Apple) so that we can maximize the following:
maxqi+qj′− τij−pi−p′j. i∈A j∈B i∈A,j∈B i∈A j∈B
With a little calculation, we can transform the above objective function as follows:
qi+qj′− τij−pi−p′j i∈A j∈B i∈A,j∈B i∈A j∈B
=(qi+qi′)− qj+qi′+ τij+pi+p′j . i∈[n] j∈B i∈A i∈A,j∈B i∈A j∈B
Note that i∈[n](qi +qi′) is a constant in this problem. Therefore, to maximize the original objective, we are to minimize the following:
min qj +qi′ + τij +pi +p′j . j∈B i∈A i∈A,j∈B i∈A j∈B
3
Then we can model this problem as a min-cut problem by constructing the graph as follows. First, we add a source node s and a sink node t. For each object j, we add one node Aj . We add an edge from S to Aj with capacity p′i +qi and add an edge from each Aj to T with capacity pj + qj′ . For the correlation between objects, we add an edge from Ai to Aj with capacity τij.
Claim: The above minimization problem has an optimal value v if and only if the above constructed network has a max-flow (min-cut) of value v.
Proof: If there is a cut of value v in the network, then actually this cut contains two parts of nodes. One part contains S and the other part contains T. Then, we just assign the objects corresponding to the nodes belonging to S to A and assign the objects corresponding to the nodes belonging to T to B. Forthecutvalue,ifnodeiisinAandnodejisinB,wewillcutthe edges from S to Aj, Ai to T and Ai to Aj. These edges are of total capacity p′j + qj + pi + qi′ + τij , which is exactly the corresponding term in the above objective function. Therefore, we can achieve v by assigning n objects to either A or B.
On the other hand, if the optimal value of the minimization problem is v, then there must be an assignment of the n objects. Then we just cut the network into two parts. One part includes S and objects in A and the other part includes T and objects in B. It is similar to the former direction to show that the cut value here equals v. Based on the above observations, we prove the claim.
Therefore, our algorithm is to first construct the above network, use Edmund- Karp (as here we require polynomial algorithm) to obtain a max-flow of that graph, traverse along the max-flow to obtain a corresponding min-cut and assign the objects belonging to S to Microsoft and the others to Apple. The construc- tion of graph, Edmond-Karp algorithm, traversing and assigning can all be done in polynomial time. The correctness is proved by the above analysis.
Rubric: 3 points for giving correct transformation of the original prob- lem. 3 points for giving the correct directed graph with capacity. 3 points for the correct claim. 3 points for the proof for each direction. (If direction and Only-if direction) (Note: if the students mention Ford-Fulkerson Algorithm with pseudo-polynomial time, give a 2 points deduction.)
4 Jumping Frogs
Somewhere near the Algorithmville, a number of frogs are standing on a num- ber of lotus leaves. As they are social animals (and yes, they are never infected by coronavirus!), the frogs would like to gather together, all on the same lotus leaf. The frogs do not want to get wet, so they have to use their limited jump distance d to get together by jumping from piece to piece. However, these lotus leaves just started to grow, they will get damaged further by the force needed to jump to another leaf. Fortunately, the frogs are real experts on leaves, and know exactly how many times a frog can jump off each leaf before it sinks and become unavailable. Landing on leaves does not damage it. You have to help the frogs find a leaf where they can meet.
4
In this question, we will get the position of N lotus leaves. For each i ∈ [N], we know its position (xi, yi), the number of frogs ni on that leaf and the number of jumps mi before it sinks. The distance between two leaves (xi, yi) and (xj , yj ) is defined as |xi − xj | + |yi − yj |. Design an polynomial algorithm to determine whether each lotus leaf can hold all frogs for a party. The output is an array with length N, containing yes/no solution.
Solution: The trick in this question is the limit of ”departure” on each leaf. To model that, we split each node to be ”departures” and ”arrivals”. The exact graph is described as follows:
• We have a source node s.
• We build N arrival nodes ai. s is linked to every ai with capacity ni.
• We build N departure nodes di. Each ai is linked to di with capacity mi.
• For a pair of leaves (i,j), we link di to aj and dj to ai, with capacity ∞, if |xi − xj| + |yi − yj| ≤ d, i ̸= j.
Then we run the Edmond-Karp (polynomial time algorithm) algorithm with source node s to sink node ai to determine that whether the max-flow value equals to Ni=1 ni. If so, we know that the leaf i is a valid spot. We repeat the max-flow algorithm for all i ∈ [N], then we can output the yes/no solution for each leaf.
Claim: The max flow value of the graph with source s and sink ai is Ni=1 ni if and only if there exist a way that all frogs gather together.
Proof: (flow value → gathering plan) To give a feasible plan from a feasible flow with value Ni=1 ni, we consider each unit flow as a frog. Surely for each leaf i, there are ni frog on it, which in the graph means that ni units flow are sent to it in the feasible flow of value Ni=1 ni. Then consider leaf i as sink and other leaf j, j ̸= i, how do we let the nj frogs arrive at leaf i? For each
5
j ̸= i, we follow the flow from aj to ai, which we assume as the following kj paths: aj → dj → ajl,1 → djl,1 → · · · → ajl,k1 →djl,k1 →ai with fl,j units flow for
l ∈ [kj]. Then we just let fl,j frogs jump from leaf j to jl,1, to jl,2 till i for all j ̸= i. This is a feasible plan as according to the construction of the graph, no more than mj units of flow can leave from aj, which means no more than mj frogs can leave from leaf j. It also makes sure that the frogs gather together at leaf i as the value of the flow is the total number of frogs. So every frog ”flows” to leaf i.
(gathering plan → flow value) For each gathering plan, we can interpret it in the similar way above. Consider a plan that all frogs gather to leaf i. Frogs on leaf j have the following kj different paths: aj → dj → ajl,1 → djl,1 → · · · → ajl,k1 →djl,k1 →ai with fl,j frogs flow for l ∈ [kj ], then we just send the corresponding value of flow along the path. This will not violate the constraints of the graph as leaf j can only handle mj leaves. In addition, the flow value is Ni=1 ni as the plan is feasible, which means that for each node i, we are sending ni units of flow.
Rubric: 5 points for giving correct directed graph with capacity. 4 points for the correct claim. 3 points for the proof for each direction. (If direction and Only-if direction) (Note: if the students mention Ford-Fulkerson Algorithm with pseudo-polynomial time, give a 2 points deduction.)
5 Preparing for the Exams
My friend Leo wants to have a emergency plan for his final exams on University of Southern Algorithmville. He has N subjects to prepare for, and for each subject, his score is determined only by the time he spend on learning. It’s not surprising that Leo found out he actually spent zero time on preparing before.
At least he knows when he can start learning all of these subjects. For each subject i there is a start time si when he can get all materials ready to
6
start learning. And there is also a ending time ei for each subject, when his learning materials expire and he can’t learn anymore. We know that si and ei are integers, and Leo can only dedicate to a single subject within each time phase.
In the University of Southern Algorithmville (USA), a student’s total grade is the minimum grade among all subjects. Leo wants you to help him find out the best outcome. Given N subjects and their time intervals (si,ei), design an algorithm to find out the maximum time possible for the least prepared subject. (Hint: It’s not enough to use the network flow algorithm alone to determine the answer.)
Solution: Consider that we want to learn for k-unit time for each subject. The problem now become determining the feasibility of learning for k time. We can build the following graph Gk:
• s is the source node.
• (The layer of subject) pi,i ∈ [N] are the nodes for each subject. We link
s → pi for every pi with a link with capacity k.
• (The layer of time intervals) We mix all starting points and ending points together to form a set {si,ei|i ∈ [N]} and de-duplicate. Finally we sort thesettogetM+1timepointsτ1 <τ2 <...<τM+1. Forexample,ifwe have {[1,5],[2,6],[2,4]}, after sorting, we have τ1 = 1,τ2 = 2,τ3 = 4,τ4 = 5,τ5 =6.
• Further, we build the nodes tj for each interval [τj,τj+1], we link an edge from pi to tj if and only if the learning time of pi contains tj , which means si ≤ τj and ei ≥ τj+1. The capacity of the link is τj+1 − τj.
• (Sink node) We build a sink node t and link all tj to t with capacity τj+1 −τj.
With the graph Gk, we run any maximum-flow algorithm from s to t.
Claim: There is feasible to study for k time if and only if the max-flow value equals k × N.
Proof: (schedule of value k exists → flow value equals Nk) We convert the schedule explicitly to a flow on Gk:
• We assign flow value k for each edge s → pi. Because we use all flow capacity from s → pj, our flow is a maximum flow with value Nk.
• The schedule for each subject i can be represented as the union of a set of intervals with length 1: {[ti,1,ti,1 +1],[ti,2,ti,2 +1],...,[ti,k,ti,k +1]}. Let the flow value for each edge pi → tj to be fij, and the value should be the length of schedule i in the interval j. Formally, it’s written as fij = |{ti,k|ti,k ≥ τj and ti,k + 1 ≤ τj+1}|.
• We assign flow value i fij from each tj to the sink node. We observe that i fij ≤ τj+1 − τj because the time schedule of each subject should not intersect with each other.
7
(Flow value equals Nk → schedule exists with value k) We only need to look through the link from subject pi to time interval tj. We note that if the flow value on the edge is fij, then we only need to assign fij time to pj within that time interval because the capacity of the outer link from tj have the capacity τj+1 − τj, for every time interval j we have i fij ≤ τj+1 − τj, which means the plan is feasible. In addition, it is a schedule with value k as all the subjects have a total time k.
Therefore, we can run binary search between [1, ⌊(τM+1 − τ1)/N⌋] to de- termine the best feasible answer k. For the chosen k, we use Edmond-Karp algorithm to compute whether there exists a max-flow of value Nk, which is in polynomial time.
Rubric: 6 points for giving correct directed graph with capacity. 3 points for the correct claim. 3 points for the proof for each direction. (If direction and Only-if direction) (Note: if the students mention Ford-Fulkerson Algorithm with pseudo-polynomial time, also give full credit to this solution. Even if the number of nodes are pseudo-polynomial (which means the reduction is pseudo- polynomial), give full credits.)
Remark: It is my fault not to clearly point out that the algorithm should be polynomial. To make sure that in your second mid-term, when you want to use NF to solve problems, always make sure that you need to make both your reduction and your algorithm polynomial if it requires you to do so.
6 Help Kumiko!
Kumiko is a member of a high school music group and she is in charge of counting the monthly community fee for each members. This work should be easy but the members are trying to make Kumiko’s life harder. They never pay the fee in an integer amount! The following form is what Kumiko has recorded.
Fortunately, Kumiko finds that the total sum of each month and of each member are integers. To make the table cleaner, she wants to round all data in the table into integers without changing any column or row sum. Therefore, no member is paying more in the table and the amount of money in each month keeps the same! Specifically, each fractional number can be rounded either up or down. For example, a good rounding for the data above would be as follows.
Your goal is to show that Kumiko can ALWAYS do the above process.
More specifically, consider there are m members, n months and a data ma-
trix {Mij}(m,n) . The sum of each row and column is integer. You want (i,j )=(1,1)
to round each entry Mij to either ⌈Mij⌉ or ⌊Mij⌋ without changing the sum of 8
Jan
Feb
Mar
Apr
Total Sum
Reina
13.12
17.04
28.92
16.92
76
Mizore
18.80
20.98
22.95
13.27
76
Shuuichi
0.08
0.98
0.13
107.81
109
Total Sum
32
39
52
138
261
Jan
Feb
Mar
Apr
Total Sum
Reina
13
17
29
17
76
Mizore
19
21
23
13
76
Shuuichi
0
1
0
108
109
Total Sum
32
39
52
138
261
each row and column. Give an polynomial time algorithm to obtain such round- ing and show the correctness of it. (Hint: (1). You can check if this kind of rounding is possible by checking whether some flow is feasible. Then show that this flow always exists. (2). You can first consider the case when Mij ∈ [0, 1] and then generalize it.)
Solution: Suppose aij is the entry in the ith row and the jth column in the table. We first consider the case when aij ∈ [0, 1]. We construct the graph as follows. The graph (network) contains one source node S and one sink node T. For every column (month) j, we create a node Cj and for every row (member) i, we create a node Ri. We add an edge from Cj to Ri with capacity 1 for all i and j. In addition, we add an edge from S to each Cj with capacity Sj = i aij, which is an integer and add an edge from each Ri with capacity Ti = j aij, which is also an integer.
It is clear to see that the value of the max flow is at most i,j aij.
Claim: If there is an integral max flow of value i,j aij, then Kumiko can have a legal rounding and vice versa.
Proof: First, if there is a feasible rounding method of the original problem, suppose the rounded entry in the ith row and the jth column is bij ∈ {0,1}. Then, we just send unit bij flow from Cj to Ri. We send unit i aij = i bij from S to Cj and send unit j aij = j bij from Ri to T for all i and j. We can easily check that it is a feasible and max flow.
On the other hand, if there is a max-flow of value i,j aij, according to the construction of the graph, all the edges from S to Cj and from Ri to T are saturated. Then we round aij to the number of unit flow sent from Cj to Ri. In this way, the sum of the ith row is the outgoing flow from the node Ri, which is the original sum and it is similar for the columns. Therefore, the existence of that flow is equivalent to the existence of possible rounding.
When it comes to general cases, instead of setting the capacity from Cj to Ri to be 1, intuitively we should set it to be [⌊aij⌋,⌈aij⌉], which is with lower bound capacity ⌊aij ⌋ and upper bound capacity ⌈aij ⌉. The equivalence between the existence of feasible rounding and the existence of a flow of value i,j aij is similar to the above case. To solve this max-flow problem with lower bound constraints, we can modify it a little bit by setting the capacity of the edge from S to Cj to be i aij − ⌊aij⌋ for all j and setting the capacity of the edge from Ri to T by j aij − ⌊aij⌋ for all i. It is an equivalent problem as the flow on edge Cj to Ri can only come from s to Cj. Then it is the same problem as the above case. Then, we can just set the capacity of the edges between Cj and Ri. Therefore, we can solve the above mentioned max-flow problem and if the value is i,j aij, we obtain a feasible rounding for each entry (which is the
9
amount of flow from Cj to Ri for aij ) in polynomial time by using Edmond-Karp algorithm.
Finally, to show that a max-flow of value i,j aij always exists, we first show that there exists a real-valued flow that achieves that one. This is trivial because by just putting aij amount of flow from Cj to Ri, we achieve the value i,j aij. Then according to Edmond Karp algorithm, we can find an integral max-flow of the same value, which proves that such rounding is always possible.
Rubric: 3 points for giving correct directed graph with capacity. 3 points for the correct claim. 3 points for the proof for each direction. (If direction and Only-if direction) 3 points for showing that there ALWAYS exists a max flow of value i,j aij . (Note: if the students mention Ford-Fulkerson Algorithm with pseudo-polynomial time, give a 2 points deduction. In addition, if students create a graph that contains pseudo polynomially many nodes, reduce 1 points in the construction of the graph.)
7 Edges that Increase Max-Flow
Given a graph G = (V,E), the source-sink pair (s,t) and capacity of edges {ce ≥ 0 | e ∈ E}, design a polynomial-time algorithm to find a set of edges S, such that for every edge e ∈ S, increasing ce will lead to an increase of max-flow value between s and t. Prove the correctness of your algorithm.
Solution: Finding the new given existing one is equivalent to finding a path on the residual network. So we break down the solution into the following steps: 1) Run Edmund-Karp algorithm to get the maximum flow of G. Subtract
the flow from the network to get Gres.
2) In Gres, s is now disconnected with t. Otherwise, according to Edmond-
Karp algorithm, we can increase the flow value by following this path. Therefore we can compute the set of connected vertices starting from s and t respectively by BFS or DFS. We name the set of vertices that corresponds to s and t to be Vs,Vt.
3)Foralledgese=(u,v)∈E,wecheckthatwhetheru∈Vs andv∈Vt. If so, increasing the flow on e will yield a path on the residual network, resulting in the increase of max-flow value between s and t.
The runtime is polynomial as we are running Edmond-Karp. BFS, DFS and checking each edge are also within poly time.
Rubric: 5 points for each step. If students use the algorithm that is trying to increase each edge with capacity 1 and run Edmond-Karp algorithm, reduce 2 points as it is still polynomial in the size the problem but uses far more time than this one.
10