1
1.
CSCI 570 – Fall 2020 – HW 8 Solution
Due October 28st 11:59pm 2020
Graded Problems
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 connectivity 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 c(S, S ̄) S⊂V
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 Cu,v v∈V,v̸=u
For each v ̸= 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. 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.
1
We claim that every client can be connected to a base station subject to load and range conditions if and only if the max flow of the above net- work 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 constraints are satisfied at every base station (respectively client ) vertex is satisfied. (note that such an assignment is unique). Further, since ev- ery 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 ex- ists 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 contribute 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.
3. Solve Kleinberg and Tardos, Chapter 7, Exercise 9.
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 ⌈n/k⌉. 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
2
1.
Practice Problems
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.
Getthemaximumflowf⋆ ,wecanfindacut(A,B),suchthatvalue(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 com- plexity is the same as that of finding the maximum flow f⋆.
3