COMP3711 - Design and Analysis of Algorithms - Assignment 5 - Solved

Q1 Converse of the Cut Lemma [10 pts]

Assume that the edges in a connected graph G = (V,E) have distinct weights. Let T = (V,E0) denote the unique MST of G.

Mathematically prove the following Lemma.

Lemma: If e ∈ E0, i.e., e is in the MST T, then there exists a subset of vertices Se ⊂ V such that e is the minimum cost edge among all edges in E with exactly one endpoint in Se.

Requirements and Comments:

•     Your proof must be “from scratch”. That is, you may not assume the correctness of any fact taught in class.

•     Your proof must be mathematically formal. Split it into small paragraphs with space between each paragraph. Make it very clear what each paragraph is assuming and proving.

•     The lemma statement above uses the terminology of the Cut Lemma taught in class. In symbols, the statement of the lemma above is that

“If e ∈ E0 then there exists some subset of vertices Se ⊂ V such that w(e) = min{w(e0) : e0 = (u0,v0) ∈ E, u0 ∈ Se, v0 6∈ Se}”.

This is the Converse of the statement of the Cut Lemma.

Q2 Generalization of Bipartite Matching [25 pts]

This problem is taken, slightly modified, from the book Algorithms by Jeff Erikson (http://algorithms.wtf)

The Department of Commuter Silence at Sham-Poobanana University has a flexible curriculum with a complex set of graduation requirements.

The department offers n different courses, and there are m different graduation requirements.

Each requirement specifies a subset of the n courses and the minimum number of courses that must be taken from that subset.

The subsets for different requirements may overlap, but each course can be used to satisfy at most one requirement (In HKUST terms, this means that a course can not be double-counted to satisfy two requirements).

As an example, suppose there are n = 5 courses {C1,C2,C3,C4,C5} and m = 2 graduation requirements:

•     You must take at least 2 courses from the subset {C1,C2,C3}.

•     You must take at least 2 courses from the subset {C3,C4,C5}.

Then a student who has only taken courses C2,C3,C4 cannot graduate, but a student who has taken either C1,C2,C3,C4 or C2,C3,C4,C5 can graduate.

Describe and analyze an O(n2m) time algorithm to determine whether a given student can or cannot graduate.

The input to your algorithm is the list of m requirements given by (i) m × n matrix Xi,j and (ii) size m array Ni and

(iii) the set of courses the student has taken, given by size n array Lj. In the three definitions below, 1 ≤ i ≤ m and 1 ≤ j ≤ n.

Xi,j
=
(

1        If course Cj is in requirement list i,

0       Otherwise
Ni
=
Number of courses that must be taken to satisfy requirement i.

(

1        If the student took course j.
Lj
=
 
                                          0     If the student did not take course j.

You may assume that you have also been given a procedure that runs the Ford-Fulkerson Max-Flow algorithm and can use that as a subroutine.

(A)     Clearly describe your algorithm for solving the problem.

(B)     Explain why your algorithm runs in O(n2m) time.

(C)      Explain why your algorithm is correct.

Q3 Max-Flow and Graph Reliability [35 pts]

Let G = (V,E) be a directed graph with two specified vertices s,t ∈ V . Assume that G contains at least one s-t path.

A subset of edges E0 ⊆ E is a separating edge set if, after removing E0 from G, no s-t path exists.

A subset V 0 ⊆ V − {s,t} of vertices is a separating vertex set if, after removing V 0 and all edges connected to V 0 from G, no s-t path exists. Note that if (s,t) 6∈ E, a separating vertex set always exists.

E0 is a smallest separating edge set if it contains the smallest number of edges among all separating edge sets. V 0 is a smallest separating vertex set if it contains the smallest number of vertices among all separating vertex sets.

Note that a smallest separating edge set E0 might not be unique. A smallest separating vertex set V 0 also might not be unique.

In the graph below {(a,f), (d,g),(e,h)} is a smallest separating edge set, but there are others as well. {g,f} and {g,a} are the only smallest separating vertex sets.

 

Smallest separating sets are indicators of failure points in a network and are therefore used in studies of network reliability.

In what follows you may use any facts or algorithms taught in class as long as you explicitly reference them (which means including their statement and where in the class or tutorial notes you found them).

(a)    Give an O(|E|2) time algorithm for finding a smallest separating edge set for G.

(b)    Assume (s,t) 6∈ E. Give an O(|V ||E|) time algorithm for finding a smallest separating vertex set for G.

Both (a) and (b) should contain 3 parts. Part (i) should describe your algorithm clearly (code is not necessary). Part (ii) should prove its correctness.

Part (iii) should derive its running time. Your proof of correctness must contain a section that EXPLICITLY justifies why your output is a smallest separating edge or vertex set.

Hints, Comments and Recommendations:

•     For (a), consider the algorithm for finding the maximum number of edge disjoint s-t paths taught in class. How can you modify that to solve this problem?

Hints. Let S,T be ANY s-t cut. Then the set of edges crossing between S,T is a separating edge set. (Prove this)

Consider the Min-Cut you get when solving the edge disjoint s-t path problem. The statement above implies that the max number of edge disjoint paths is an upper bound on the size of the smallest separating edge set (why?). Can you show that these two values must be equal?

•     For (b), modify G to create a new graph G0 = (V 0,E0).

(i)        For every vertex v ∈ V, create two vertices v`,vr in V 0.

(ii)      For every vertex v ∈ V − {s,t}, Create edge (v`,vr) in E0.

(iii)    For every edge (u,w) ∈ E, create edge (ur,w`) in E0.

(iv)    Remove vertices s` and tr from V 0.

Note that if P is an s − t path in G that passes through vertex v, the corresponding path P 0 in G0 is an sr −t` path that passes through edge

(v`,vr).

•     The modified graph G0 contains two very different type of edges:

E10             = {(v`,vr) : v ∈ V − {s,t}}, E20       = {(ur,v`) : (u,v) ∈ E}.

A separating vertex set in G corresponds to a separating edge set in G0 in which all edges are in  and vice-versa.

So solving (b) corresponds to finding a smallest separating edge set in which all edges are in  .

The idea is to appropriately modify the algorithm for part (a) to find such a set.

•     Suppose you assign capacity 1 to all edges in  and capacity 2 to all edges in . Prove that the edges crossing a Min-Cut must all be of type .

(Proving this requires understanding the structure of the min-cut in the proof of the correctness of the Ford-Fulkerson algorithm.)

•     Use the observations above and (a modified version of) the result of part (a) to solve (b).

Q4 All-Pairs Shortest-Paths [10 pts]

Let G = (V,E) be the directed weighted graph shown below with its associated weighted adjacency matrix.

0
8
10
∞
3
∞
6
0
∞
3
∞
∞
∞
∞
0
∞
1
∞
∞
∞
∞
0
2
10
∞
2
∞
∞
0
2
∞
∞
5
1
∞
0
 





W = 







This problem asks you to solve the all-pairs shortest-path problem on this graph in two different ways.

(a)    Run the 2nd dynamic-programming solution from the slides on this graph. Recall that in the 2nd dynamic-programming solution

 

where   and, in general, D(m) is the matrix

 . For this problem you need to fill in the matrices D(2), D(4) and the final solution D(8)(= D(5)).

                                                                                                                     

                                                                                                                  

                                                                                                                  

D(2) =  D(4) =  D(8) = 

                                                                                                                  

                                                                                                                  

                                                                                                                  

(b)    Now run the Floyd-Warshall algorithm on the graph. Recall that in the Floyd-Warshall algorithm

 

where d0ij = wij so D(0) = W, and D(m) is the matrix  . For this problem you need to fill in the matrices D(i), where i = 1,2,3,4,5,6 and D(6) is the final solution.

 

 

Q5 The Ford-Fulkerson Algorithm [20 pts]

Consider the graph below with the given capacities.

Start with a flow that has f(e) = 0 for every edge and run the FordFulkerson Max Flow Algorithm on the graph below to find a max-flow from s to t

 

(a)    Show every step of the algorithm. That is, for every step show the current flow f, its associated residual graph Gf and the augmenting path P you choose, along with the value cf(P).

All of the information for each step should be on the same page. (If it’s not too crowded, try putting all of the information for two steps on each page.)

(b)    Show your final flow and provide a cut with capacity equal to that of the flow.

Note: If you don’t have access to another drawing tool you may use the PPT slide we provide as the basis for your drawing, editing/copying it to show all of the intermediate residual and flow graphs.