Algorithms 3027/3927 Assignment 1 v2 The University of Sydney 2019 Semester 1 School of Computer Science
Description
Consider the following variant of the MST problem. We are given an undirected, complete graph G = (V, E) with n vertices and m = n edges, a positive (not necessarily unique) edge cost ce for each edge
2
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 degF (u) = 1 for each u ∈ A (i.e. every u ∈ A has degree 1 in the graph (V, F )).
Task 1: [20 marks]
Show that simply computing the MST does not work. In particular, show that there is a graph G = (V, E) with edge costs ce and a subset of vertices A V such that the minimum spanning tree X for this graph has degX(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. thesubsetAV,
3. a minimum spanning tree X, and
4. avertexu∈AsuchthatdegX(u)>1.
Task 2: [20 marks]
We will now develop some insight into the structure of the optimal solution. Consider an optimal solution F and let FA ⊆ F be the set of edges in F incident to vertices in A. Prove that (V \A, F \FA) is connected graph and moreover, is a minimum spanning tree of the complete subgraph of G on the vertices V \ A.
Task 3: [60 marks]
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”). [20 marks]
2. Argue why your algorithm is correct. [20 marks]
3. Prove an upper bound on the time complexity of your algorithm. [20 marks]
Submission details
• Submission deadline is Wednesday 20th March, at 23:59. Late submissions without special consideration will be subject to the penalties specified in the first lecture (5% per day). Also note that as graded submissions and solutions will be given out on Thursday 28th March, we will not accept any submission later than Wednesday 27th March, 23:59.
• Submit your answers to Tasks 1, 2, 3 as a single document to Canvas. Your work must be typed (no images of text, although you can use diagrams if you think it helps.) Please try to be reasonably concise (one to two pages of a4).
• Your report will be subject to automatic and manual plagiarism detection systems. Remember, it’s acceptable to discuss high level ideas with your peers, but you should not share the detail of your work, such as parts as the precise algorithms, examples, proofs, writing, or code.
• To facilitate anonymous grading, please do not write your name on your submission.
1