CSCI 570 – Summer 2020 – HW 5 Solutions
1 Graded Problems
1. State True/False: For any flow network G and any maximum flow on G,
there is always an edge e such that increasing the capacity of e increases
the maximum flow of the network. Justify your answer.
Answer: False, Consider a counter-example graph G. It has three nodes
s, t, v. s is the source node and t is the sink node. It has two edges
(s, v), (v, t) and each edge has a capacity of 1. The max-flow is 1 and
increasing the capacity of any edge won’t increase the max-flow.
2. Suppose that you are given a flow network G, and G has edges entering
the source s. Let f be a flow in G in which one of the edges (v, s) entering
the source has f(v, s)=1. Prove that there must exist another flow f ′
with f ′(v, s) = 1 such that |f | = |f ′|. Give an O(|E|)-time algorithm to
compute f ′, given f, and assuming that all edge capacities are integers.
Answer: First thing to notice is that a cycle p containing s and v exists in
f . One can construct the other flow f ′ as follows:∀(v1, v2) ∈ p, f ′(v1, v2) =
f(v1, v2) − 1 . Obviously, f ′(v, s) = 0. Since the incoming flow value of
the source decrease by 1 and the outcoming flow value also decrease by 1,
we have |f | = |f ′|. Now we need to show f ′ is valid. Since we decrease the
flow value of each edge in the cycle p, all the nodes in the cycle p (except
the source s) still have Σf(v, .) = Σf(., v),∀v ∈ p, v 6= s. Besides, since
f(v, s) = 1, the new flow value of each edge in p will be at least 1. Thus,
the new flow value of each edge in p will be larger or equal to 0. Since
we are decreasing the flow value, so the new flow value of each edge will
not exceed its capacity. One can find a cycle starting at s in O(|E|) time
(using BFS/DFS). Once the loop is found, the rest can also be done in
O(|E|) time.
3. Suppose that you wish to find, among all minimum cuts in a flow network
G with integral capacities, one that contains the smallest number of edges.
Show how to modify the capacities of G to create a new flow network G′ in
which any minimum cut in G′ is a minimum cut with the smallest number
of edges in G.
Answer: Denote c(e) to be the capacity of edge e in G = (V,E) and
c′(e) be the capacity of the same edge e in the new constructed graph
1
G′ = (V,E). To achieve the goal, one modification is that c′(e) = c(e)+ δ.
We will show δ = 1|E|+1 will satisfy the requirements. Denote the min-cut
with least number of edges in G has n edges and its cut value is m. The
new value of the cut is m+ n× δ.
Case 1 For a min-cut in G which has more edges than n, it won’t be a
min-cut in G′.
Case 2 For any other cut in G that has n′ edges, we need to show that
it won’t be a min-cut in the new graph G′. Support its cut value in G is
m′. Since the capacities are all integer and m′ > m, we have m′ ≥ m+ 1.
Its cut value in the new graph G′ will be m′ + n′ × δ. Replacing δ with
1
|E|+1 , we have
m+ n× δ < m+ |E| × δ < m+ 1 ≤ m′ < m′ + n′ × δ. Thus, any other cut in G that’s not a min-cut won’t be a min-cut in the new graph G′. 4. Solve Kleinberg and Tardos, Chapter 7, Exercise 7. Answer: The problem is equivalent to solving max-flow in the following graph. The graph is construct so that there are n+ k + 2 nodes • there’s a source node s and a sink node t. • the i− th client has a node, say ui. • the j − th station has a node, say vj . • for each client node u, there’s an edge (s, u) with capacity 1. • for each station node v, there’s an edge (v, t) with capacity L. • if the distance between i − th client and j − th station is within r, there’s an edge (ui, vj) with capacity 1. We then compute the max-flow of the constructed graph. If the value of the max-flow is n, then we can find the arrangement. The graph has O(n + k) nodes and at most O(nk) edges. The running time will be polynomial. 5. At a dinner party, there are n families a1, ..., an and m tables b1, ..., bm. The i− th family ai has gi members and the j − th table bj has hj seats. Everyone is interested in making new friends and the dinner party planner wants to seat people such that no two members of the same family are seated in the same table. Design an algorithm that decides if there exists a seating assignment such that everyone is seated and no two members of the same family are seated at the same table. Answer: Construct the following network G = (V,E). For every family introduce a vertex and for every table introduce a vertex. Let ai denote the vertex corresponding to the i− th family and let bj denote the vertex 2 corresponding to the j − th table. From every family vertex ai to every table vertex bj , add an edge (ai, bj) of capacity 1. Add two more vertices s and t. For every family vertex ai add an edge (s, ai) of capacity gi. For every table vertex bj add an edge (bj , t) of capacity hj . Claim:There exists a valid seating if and only if the value of max flow from s to t in the above network equals Σ1≤i≤ngi. Proof. Assume there exists a valid seating, that is a seating where every one is seated and no two members in a family are seated at a table. We construct a flow f to the network as follows. If a member of the i − th family is seated at the j − th table in the seating assignment, then assign a flow of 1 to the edge (ai, bj). Else assign a flow of 0 to the edge (ai, bj). The edge (s, ai) is assigned a flow equaling the number of members in the i − th family that are seated (which since the seating is valid equals gi). Likewise the edge (bj , t) is assigned a flow equaling the number of seats taken in the table bj (which since the seating is valid is at most hj). Clearly the assignment is valid since by construction, the capacity and conservation constrains are satisfied. Further, the value of the flow equals g1 + g2 + ...+ gn. Conversely, assume that the value of the max s-t flow equals g1+g2+...+gn. Since the capacities are integers, by the correctness of the Ford- Fulkerson algorithm, there exists a max flow (call f) such that the flow assigned to every edge is an integer. In particular, every edge between the family vertices and table vertices has a flow of either 0 or 1 (since these edges are of capacity 1). Construct a seating assignment as follows: seat a person of the i − th family at the j − th table if and only if f(ai, bj) is 1. By construction at most one member of a family is seated at a table. Since the value of f equals the capacity of the cut (s, V − s), every edge out of s is saturated. Thus by flow conservation at ai, for every ai the number of edges out of ai with a flow of 1 is gi. Thus in the seating assignment, every one is seated. Further, since the flow f(bj , t) out of bj is at most hj , so at most hj people are seated at table bj . Thus we have a valid seating. 6. There is a precious diamond that is on display in a museum at m disjoint time intervals. There are n security guards who can be deployed to protect the precious diamond. Each guard has a list of intervals for which he/she is available to be deployed. Each guard can be deployed to at most A time slots and has to be deployed to at least B time slots. Design an algorithm that decides if there is a deployment of guards to intervals such that each interval has either exactly one or exactly two guards deployed. Answer: We create a circulation network as follows. For the i−th guard, introduce a vertex gi and for the j − th time interval, introduce a vertex tj . If the i − th guard is available for the j − th interval, then introduce an edge from gi to tj of capacity 1. Add a source s and a sink t. To 3 every guard vertex add an edge from s of capacity A and lower bound B. From every interval vertex add an edge to t of capacity 2 and lower bound 1. Add an edge from t to s of infinite capacity. We claim that there exists a valid deployment if and only if the above network has a valid circulation. The proof of the claim is virtually identical to the proof in section 7.8 of the text for the survey design problem. The algorithm proceeds by determining if the network has a circulation (by reducing it to a flow problem and then applying Ford-Fulkerson) and answers “yes” if and only if there is a circulation. The number of vertices and number of edges in the resulting flow problem are bounded by O(n) and O(n2) respectively. The running time of our algorithm is dominated by the flow computation which takes O(n3). 7. An edge of a flow network G is called critical if decreasing the capacity of this edge results in a decrease in the maximum flow. Is it true that with respect to a maximum flow of G, any edge whose flow is equal to its capacity is a critical edge? Give an efficient algorithm that finds a critical edge in a flow network. Answer: Not true. Consider a flow graph G = (V,E) such that V = {a, b, s, t}, E = {(s, a), (a, b), (a, t), (b, t)} and the capacity of each edge is 1. The maximum flow is 1 and an alternative path from a to b can be found if one path gets blocked. For a flow network, for a max-flow f , we can find a cut (A,B) such that value(f) = cap(A,B). Assume that A contains source and B contains target. An edge ec from A to B can be found such that f(ec) = c(ec) in f, then ec is a critical edge. Proof. Since cap(A,B) = ΣeioutofAc(ei), and ec ∈ {ei}, reducing c(ec) will then reduce the capacity of cut (A,B) from cap(A,B) to cap′(A,B). Orig- inally, value(f) = cap(A,B). After the reduction, the modified maximum- flow f ′ will satisfy this relation: value(f ′) ≤ cap′(A,B) < cap(A,B) = value(f). Thus ec is a critical edge. The algorithm can be implemented as follows. After finding the maximum flow f , perform DFS from the source node on Gf , and label the reachable nodes as A. Label the rest of the nodes as B. Scan all the edges in G. If an edge goes from A to B, then that edge is an critical edge. DFS runs in O(|V |+ |E|), and scanning takes O(|E|). So the final complexity is the same as that of finding the maximum flow f . 4