Question

Trying to Divide and Conquer

In this question we are trying to apply our favourite divide-and-conquer technique to the MST finding problem.
Here's my attempted solution, on a graph G = (V,E), with V = {v1, ..., Un} where n > 2:
getMST (V, E):
0. if n = 1: return E
1. i floor (n/ 2)
2. V_S = {v_1, ..., v_i}
3. V_T {v_{i+1},
v_n}
4. E_S= edges from E that contain only vertices in S
5. E_T = edges from E that contain only vertices in T
6. MST_S= getMST (V_S, E_S)
7. MST T= getMST (V_T, E_T)
8. e
:= edge in E from V_S to V_T with minimum weight
9. MST MST_S + MST_T + e
10. return MST
Prove, with the same level of rigour as in our lecture proofs, that this algorithm produces a MST, or show that
it does not.

Answer 1

The student's divide-and-conquer approach to finding a Minimum Spanning Tree (MST) is flawed because it does not guarantee that the minimum weight edge connecting subsets creates a valid MST without introducing cycles or excluding vertices.

Step-by-step explanation:

The student is attempting to apply the divide-and-conquer technique to the problem of finding a Minimum Spanning Tree (MST) on a graph G = (V,E), with vertex set V and edge set E. The approach involves recursively finding MSTs for subsets of the graph, and then connecting these with the minimum weight edge between the two subsets.

However, the algorithm described is flawed. Particularly, after obtaining MST_S and MST_T, simply choosing the minimum weight edge e between V_S and V_T and adding it to the union of MST_S and MST_T is not guaranteed to result in a MST for the entire graph. The correct approach requires ensuring that the selected edge e does not create a cycle when added to the combined MST_S and MST_T, and that every vertex in V is included in the final MST with the minimum possible total edge weight. Without this verification step, the algorithm cannot guarantee an optimal solution.