24-2.
a.
Let box x = (x1 , x2 , . . . , xd ), box y = (y1 , y2 , . . . , yd ) and box z = (z1 , z2 , . . . , zd ) such that x nests within y and y nests within z.
We need to prove that x also nests within z. By the definition of nesting, there exists permutations π and σ of{1, 2, . . . , d}, such that xπ(i) < yi , yσ(i) < zi , for all i ∈ {1, 2, . . . , d}. Let τ be the permutation such that τ (i) = π(σ(i)). Then we have xτ (i) = xπ(σ(i)) < yσ(i) < zi for all i ∈ {1, 2, . . . , d}. Thus x nests within z and the nesting relation is transitive.
b.
Let box x = (x1 , x2 , . . . , xd ) nesting within a box y = (y1 , y2 , . . . , yd ), i.e. there exists a permutations π such that xπ(i) < yi for all i ∈ {1, 2, . . . , d}.
Without loss of generality, we assume that y1 , y2 , . . . , yd are sorted in increasing order. We claim that for the permutation σ such that xσ(1) , xσ(2) , . . . , xσ(d) are in increasing order, it holds that xσ(i) < yi for all i ∈ {1, 2, . . . , d}.
Proof:
Assume for contradiction that there is a j ∈ {1, 2, . . . , d} such that xσ(j) ≥ yj . Since σ sort the dimensions of x in increasing order, only j − 1 dimensions of x are less than yj .
This contradicts the condition that y1 , y2 , . . . , yd are sorted in increasing order: since yj ≥ yi for all i ≤ j, yj > xπ(i) for all i ≤ j, i.e. there are at least j dimensions of x that are less than yj . Therefore our claim is correct.
We can write the following algorithm based on the claim:
IS-NESTING(x,y):
Sort the dimensions of the boxes in increasing order (x1 , x2 , . . . , xd ) and (y1 , y2 , . . . , xd ) for i ← 1 to d do
if xi ≥ yi then
return false
return true
Complexity : O(dlogd)
c.
Construct a graph G = (V, E), where each vertex vi corresponds to the box Bi , and (vi , vj) ∈ E if and only if Bi nests within Bj . The graph G is a DAG because nesting is transitive and anti- reflexive.
Add a super-source vertex s and a super-sink vertex t to G, and add edges (s, vi) for all vertices vi with in-degree 0 and (vj , t) for all vertices vj with out-degree 0. Call the resulting DAG G’. Use the algorithm DAG-SHORTEST-PATHS to find a longest path from s to t in the DAG G’ . This path corresponds to a longest sequence of nesting boxes.
The time for constructing G is O(dn2 + dn log d), from comparing each of the nC2 pairs of boxes after sorting the dimensions of each. The time for adding s, t and their incident edges is O(n). The time to find a longest path in G’ is O(n2 ), since G has n + 2 vertices and O(n2 ) edges. So the overall time complexity is O(dn2 + dn log d).
24-6.
Bitonic sequence can either
1. increase, then decrease, then increase, or
2. decrease, then increase, then decrease.
In order to find the shortest paths satisfying (1), we call INITIALIZE- SINGLE-SOURCE and then perform three passes of relaxing: in the first and third passes, we relax every edge in increasing order of weight, and in the second pass we relax every edge in decreasing order of weight. By the uniqueness of edge weights, the ordering of relaxing is unique.
Recall path-relaxation property Lemma 24.15. It guarantees that we would have computed correct shortest paths from s to each vertex satisfying (1).
Similarly, to find the shortest paths satisfying (2), we relax every edge in decreasing order of weight in the first and third passes, and relax every edge in increasing order of weight in the second pass.
25-1.
a.
Let T be the|V|×|V| boolean matrix representing the transitive closure. Update T as follows when an edge (u, v) is added to G:
UPDATE-TRANSITIVE-CLOSURE(u,v):
for i ← 1 to|V| do
for j ← 1 to|V| do
if T [i, u] = 1 and T [v, j] = 1 then
T [i, j] ← 1
b.
Insert the edge (vn , v1 ) into the straight-line graph v1 → v2 → · · · → vn , where n =|V|. Before the insertion, n(n + 1)/2 entries in T are 1. After the edge is inserted, all the n2 entries in T are 1. Hence Ω(|V|2 ) entries must be changed in T , which requires Ω(|V|2 ) time.
c.
Observe in the algorithm from Part a, the loop over j is not useful when T [i, v] = 1, since adding the edge (u,v) does not make any new vertices reachable from i if there already exists a path from i to v.
Thus, we can update or revise the algorithm as following: UPDATE-TRANSITIVE-CLOSURE(u,v):
for i ← 1 to|V| do
if T [i, u] = 1 and T [i, v] = 0 then for j ← 1 to|V| do
if T [v, j] = 1 then
T [i, j] ← 1
Consider any sequence of n insertions, the total time used by the first two lines is O(n|V|) = O(|V|3) (note that n ≤|V|2 since there cannot be more than|V|2 edges in G).
Notice that the inner loop on j is executed only when T [i, v] = 0, and in that case, the last line will set T [i, v] ← 1. Thus, the number of 0 entries in T is reduced by at least 1 each time the inner loop is executed Since there are|V|2 entries in T , the inner loop is executed at most O(|V|2 ) times, costing O(|V|3) time in total.
Hence the overall time complexity is O(|V|3).
26-1.
a.
Given a flow network G where vertices have capacities, we can obtain an ordinary flow network G’ by replacing each vertex v in G with two vertices v1 , v2 in G’ : we replace any edge coming into v in G with an edge coming into v1 in G’ with the same capacity, replace any edge going
out from v in G with an edge going out from v2 in G’ with the same capacity, and add an edge (v1 , v2 ) with the capacity of v in G. Now any valid flow in G is also a valid flow in G’ and vice versa.
b.
Given an instance of the escape problem, we can construct a flow network G with anti-parallel edges and vertices capacities, such that
1. For each vertex in the grid, add a vertex in G with capacity 1;
2. For each edge {u, v} in the grid, add two anti-parallel edges (u, v) and (v, u) in G, both with capacity 1;
3. Add a super source vertex s and edges (s, v), each with capacity 1, for all vertices v in G corresponding to a starting point in the escaping problem;
4. Add a super sink vertex t and edges (w, t), each with capacity 1, for all vertices w corresponding to boundary points in the grid. An escape problem has a solution if and only if the value of the maximum flow in G is equal to the number m of starting points.
Using Part a to remove vertex capacities and the method in Section 26.1 to remove anti- parallel edges, we obtain an ordinary flow network G’ equivalent to G. We can then solve the escape problem by solving the maximum flow problem on G’ and check its value. Construction of G takes O(n2 ) time as there are O(n2 ) vertices and O(n2 ) edges. Applying Part a takes O(n2 ) time, since constant time is required per vertex as the degree of each vertex is at most 4.
Applying the transformation in Section 26.1 takes O(n2 ) time since there are O(n2 ) pairs of anti-parallel edges. The ordinary flow network G’ has O(n2 ) vertices and O(n2 ) edges since the transformations only multiply the number of vertices and edges by a constant number. Using the Ford – Fulkerson algorithm to find a maximum flow in G’ takes O(mn2 ) time. So the overall time complexity is O(|E||f|) = O(mn2 ).
26-4.
a.
Execute one iteration of the Ford-Fulkerson algorithm.
Proof of correctness:
Increasing the capacity of one edge by 1 increases the minimum edge cuts by at most 1, i.e. increases the value of a maximum flow by at most 1.
On the other hand, each augmenting path increases the flow by at
least 1, therefore one iteration is enough to update the maximum flow.
b.
Let f be a maximum flow before reducing the capacity of (u, v). If f (u, v) is less than or equal to the reduced capacity c(u, v), we do nothing. Otherwise, we have f (u, v) > 0. First, we check whether there is an augmenting path from u to v. If so, we can reduce f (u, v) by 1 and reroute this one unit of flow via the augmenting path from u to v, and the total flow value is not changed. If there is no augmenting path from u to v, we find an augment path from u to s to reduce the flow from s to u by 1, find an augmenting path from v to t to reduce the flow from v to t by 1, and reduce f (u, v) by 1. Now we have a new flow with value decreased by 1. In both cases, the running time is O(|V| +|E|) since finding an augmenting path takes O(|V|+|E|) time with DFS or BFS.