np-completeness in the bounded degree spanning tre

问题:

I understand why the Bounded Degree Spanning Tree is considered NP Complete with a degree or 2 (it is an instance of the Hamiltonian Path Problem), but I do not understand why this applies to degrees > 2. If someone could please explain why this is an NP Complete problem for degree > 2, It would be most helpful

回答1:

Well, I think that you can make a simple reduction from the instance of bounded by 2, to the instance of General k.

Intuitivly, we will connect to each node of the original graph new k-2 nodes. Therefore every spanning tree will have to contain the k-2 edges from the original node to the new nodes that we connected to him, and a spanning tree from degree at most k exists if there is a spanning tree of degree at most 2 for the original graph.

The formal reduction will be:

F(V,E)=(V',E'), when : V'={(v,i)|v is in the original graph, 0 < i < k+1), E' = E U {((v,0),(v,i))}, and I don't write a formal proof for the correctness because after all we are not in a math forum.

Good luck and hope that it helped :)