CSCI 570 – Summer 2021 – HW 4 Solution
1 Graded Problems
1. The edge connectivity of an undirected graph is the minimum number of edges whose
removal disconnects the graph. Describe an algorithm to compute the edge connectiv-
ity of an undirected graph with n vertices and m edges in O(m2n) time.
For a cut (S, S̄), let c(S, S̄) denote the number of edges crossing the cut. By definition, the
edge connectivity
k = min
S⊂V
c(S, S̄)
Fix a vertex u ∈ V . For every cut (S, S̄), there is a vertex v ∈ V such that u and v are on either
side of the cut. Let Cu,v denote the value of the min u-v cut. Thus
k = min
v∈V,v 6=u
Cu,v
For each v 6= u, Cu,v can be determined by computing the max flow from u to v. Since G is
undirected, we need to implement an undirected variant of the max flow algorithm. Set all edge
capacities to 1. During each step of the flow computation, search for an undirected augmenting
path using breadth first search and send a flow of 1 through this path.
There are n− 1 flow computations and each flow computation takes at most O(m2) time.
2. At a dinner party, there are n families a1, a2, …, an and m tables b1, b2, …, 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.
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 corresponding to the jth 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∑
n≥i≥1 gi Proof of Claim: 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 ith family is seated at the jth 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 ith 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 ith family at the jth table if and only if f(ai, bj) is 1. By construction at most one member of
1
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.
3. There is a precious diamond that is on display in a museum at m disjoint time inter-
vals. 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.
We create a circulation network as follows. For the ith 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 jth interval, then introduce
an edge from gi to tj of capacity 1. Add a source s and a sink t. To 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).
4. Solve Kleinberg and Tardos, Chapter 7, Exercise 7.
Let s be a source vertex and t a sink vertex. Introduce a vertex for every base station and
introduce a vertex for every client.
For every base station vertex b, add an edge (s, b) of capacity L. For every client vertex v, add
an edge (v, t) of unit capacity. For every base station vertex b, add a unit capacity edge from b to
every client c within its range.
We claim that every client can be connected to a base station subject to load and range con-
ditions if and only if the max flow of the above network is at least n.
If every client can be connected to a base station subject to load and range conditions, then if
a client c is served by base station b, assign a unit flow to the edge (b, c). Assign the the flows to
the edges leaving the source (respectively the edges leaving the sink) so that the conservation con-
straints are satisfied at every base station (respectively client ) vertex is satisfied. (note that such
an assignment is unique). Further, since every client can be connected to a base station subject to
load conditions, the capacity constraints at the edges leaving the source are also satisfied. Hence
we are left with a valid flow assignment for the network. Since every client is connected, the flow
entering the sink is at least the number of clients n (in fact, it is exactly n).
Conversely, if the max flow of the network is at least n then there exists a integer flow of flow
value at least n (since all capacities are integral). We will work with this integral flow. For every
edge (b, c) with a flow of 1, assign c to the base station b. Since a client vertex can at most con-
tribute one unit of flow entering t, and the total flow entering t is at least n, every client vertex
has flow entering it. This implies that every client is serviced by exactly one station. Since the
flow entering a base station vertex b is at most L, a base station is assigned to at most L clients.
Thus every client is connected to a base station subject to load and range conditions.
Hence our claim is true and all that is left to do is to compute the max-flow of the network
using Ford-Fulkerson and to output YES if and only if the max-flow value is at least n.
5. Solve Kleinberg and Tardos, Chapter 7, Exercise 9.
2
This problem is virtually identical to the previous problem. Let s be a source vertex and t a
sink vertex. Introduce a vertex for every hospital and introduce a vertex for every injured-person.
For every hospital vertex h, add an edge (s, h) of capacity dn/ke. For every injured-person vertex
c, add an edge (c, t) of unit capacity. For every hospital vertex h, add a unit capacity edge from h
to every injured-person vertex c within half-hour’s driving.
We claim that every injured person can be admitted to a hospital (within 1/2 hour driving) such
that the load on the hospitals are balanced if and only if the max flow of the above network is at
least n. The proof is identical to the previous problem.
2 Practice Problems
1. 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.
Not true.
As shown below. The maximum flow is 1, and an alternative path from M to T can be found if
one path gets blocked.
Get the maximum 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) =
∑
eioutofA
c(ei) , and ec ∈ {ei}, reducing c(ec) will then reduce the capacity of
cut A, B from cap(A,B) to cap
′
(A,B).
Originally, 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.
Implementation:
After finding the maximum flow f?, do DFS from 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.
Complexity: DFS is O(n + m), and scanning is O(m). So the final complexity is the same as that
of finding the maximum flow f?.
3