Consider the following decision problems: • Minimum-Spanning-Tree: Given a weigh
ID: 3902376 • Letter: C
Question
Consider the following decision problems:
• Minimum-Spanning-Tree: Given a weighted graph G = (V, E) and an integer d, does there exist a spanning tree of G with weight at most d?
• Minimum-Spanning-2-Forest: Given a weighted graph G = (V, E) and an integer d, does there exist a pair of subtrees T1 = (V1, E1) and T2 = (V2, E2) of G, such that V2 = V V1 (i.e. each vertex of G is in either T1 or T2), and the weight of the two trees sum to at most d?
(i) Prove that Minimum-Spanning-2-Forest ?P Minimum-Spanning-Tree (you may assume that the weights are positive and that the graph has at least 2 vertices)
(ii) Use this reduction to help you prove that Minimum-Spanning-2-Forest ? P
Explanation / Answer
Problem 1: We are given with weighted graph G = (V, E)
We can modify the kruskal's algorithm by introducing a sum variable to keep track of the length of the minimum spanning tree formed as follows:
Finally we get the minimum spanning tree. Now make the following comparison:
If SUM <= d, it is proved that such a spanning tree of G exists, else it doesn't exist.
Therefore, the problem is decidable.
Please ask the second question as a separate post. Thank you.