Question

The $\mathbf{k}\mathbf{-}$SPANNING TREE problem is the following.Input: An undirected graph $\mathbf{G}\mathbf{=}\left(V,E\right)$ Output: A spanning tree of $\mathbf{G}$ in which each node has degree $\mathbf{\le }\mathbf{k}$, if such a tree exists.Show that for any $\mathbf{k}\mathbf{\ge }\mathbf{2}$:

1. $\mathbf{k}\mathbf{-}$ SPANNING TREE is a search problem.
2. $\mathbf{k}\mathbf{-}$ SPANNING TREE is NP-complete. (Hint: Start with $\mathbf{k}\mathbf{=}\mathbf{2}$ and consider the relation between this problem and RUDRATA PATH.)

Short answer

1.$k-$ SPANNING TREE is a search problem for any $k\ge 2$.

2.$k-$SPANNING TREE is NP-complete.

Step-by-step solution

Explain Spanning tree

Consider that the spanning tree is a subset of a Graph $G$ that covers all of the vertices with the fewest number of edges feasible. It can be deduced from this definition that every linked and undirected Graph $G$contains at least one spanning tree

To prove that k−  SPANNING TREE is a search problem

Consider the given input and output with $k\ge 2$.

Here, it is important to demonstrate that given a solution $S$ to the spanning tree problem that can be checked in polynomial time whether it is in fact a k-spanning tree. This comments to verifying that every node in the original graph is used in $S$ such that $S$ have no cycle because it is a tree.

Every node in the tree has a maximum degree $k$ . All of these can be checked efficiently and therefore the $k-$ spanning tree is a search problem.

Therefore, it can be concluded that for $k\ge 2$, the $k-$spanning tree is a search problem.

To prove that k -SPANNING TREE is NP-Complete problem

Any of a class of computer problems for which no efficient solution algorithm has been developed is known as an NP-complete issue.From part (a) it is known that the $k-$spanning tree is in NP.

In the Rudrata path algorithm, assume $G$ is an unweighted undirected graph. Add weights equal to 1 on every edge of $G$ while executing the Rudrata path algorithm with $k=2$ .It is observed that a tree that has each vertex with a degree at most $2$ is a path. Hence, there is no path without loops that reaches all the vertices so there will be no Rudrata path.

Therefore, it can be concluded that the Rudrata path is reduced to a $k-$spanning tree along with the fact that the $k-$spanning tree is in NP.