Reference no: EM132252057

Assignment -

Description - Consider the following variant of the MST problem. We are given an undirected, complete graph G = (V, E) with n vertices and m = edges, a positive (not necessarily unique) edge cost c_e for each edge in E. We are also given a subset of vertices A V. The goal is to find a minimum cost set of edges F ⊆ E such that (V, F) is connected, and deg_F(u) = 1 for each u ∈ A (i.e. every u ∈ A has degree 1 in the graph (V, F)).

Task 1: Show that simply computing the MST does not work. In particular, show that there is a graph G = (V, E) with edge costs c_e and a subset of vertices A V such that the minimum spanning tree X for this graph has deg_F(u) > 1 for some u ∈ A. Your task is to give such a graph on three vertices x, y, z. You need to specify:

1. the edge weights c_(x,y), c_(y,z), c_(z,x),

2. the subset A V,

3. a minimum spanning tree F, and

4. a vertex u ∈ A such that deg_F(u) > 1.

Task 2: We will now develop some insight into the structure of the optimal solution. Consider an optimal solution F and let F_A ⊆ F be the set of edges in X incident to vertices in A. Prove that (V\A, F\F_A) is connected graph and moreover, is a minimum spanning tree of the complete sub-graph of G on the vertices V \ A.

Task 3: Use the insight gained in Task 2 to design an algorithm that solves this problem in O(m log n) time.

1. Description of how your algorithm works ("in plain English").

2. Argue why your algorithm is correct.

3. Prove an upper bound on the time complexity of your algorithm.

Note - Must be text typed within 1-2 A4 pages.

Attachment:- Assignment File.rar