Spanning Trees:
The k-Spanning Tree problem takes as input an undirected graph Gand produces as output a spanning tree of G in which every node hasdegree ≤ k (if such a tree exists).
In this problem you will prove that, for any k ≥ 2, thek-Spanning Tree problem is NP complete.
(1)
Suppose that you have an undirected graph G and are given aproposed solution for the k-Spanning Tree problem for some value ofk ≥ 2. In two or three precise sentences, explain what you wouldhave to do to verify the proposed solution.
(2)
The 2-Spanning Tree problem is identical to the Rudrata Pathproblem, which is known to be NP complete.
Let’s reduce the 2-Spanning Tree problem to the 3-Spanning Treeproblem. The first step in the reduction is to convert a graph G,intended as input to the 2-Spanning Tree problem, into a graphf(G), intended as input to the 3-Spanning Tree problem.
It is possible to design a correct f(G) that operates byapplying a simple operation to each vertex of G. In one sentence,explain what this operation is.
(3)
The second step in the reduction is to convert a 3-spanning treeT for f(G) into a 2-spanning tree h(T) for G.
It is possible to design a correct h(T) that operates byapplying a simple operation to each vertex of T. In one sentence,explain what this operation is.
(4)
You have just proven that the 3-Spanning Tree problem is NPcomplete. In two or three precise sentences, explain how you wouldprove that the k-Spanning Tree problem is NP complete for all k ≥2.
Expert Answer
Answer to Spanning Trees: The k-Spanning Tree problem takes as input an undirected graph G and produces as output a spanning tree …