Consider the following decision problems: • Minimum-Spanning-Tree: Given a weigh

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.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.