NP-completeness of a spanning tree problem

Problem Detail: 

I was reviewing some NP-complete problems on this site, and I meet one interesting problem from

NP completeness proof of a spanning tree problem

In this problem, I am interested in the original problem, which the leaf set is precisely $S$. The author said that he can prove this by reducing it to the Hamiltonian path. However, I still cannot figure it out. Could anybody help me with this in details?

Asked By : breezeintopl

Answered By : hugomg

Seems this question has been bumped by the system because it has no answer yet:

The idea JeffE proposed is to reduce the Hamiltonian Path problem (a known NP-complete problem) to this version of the spanning tree problem.

This is not hard to do: given a graph and two nodes we want to find an HPath between, we can set S to the set containing those two nodes and ask for a spanning tree with those nodes as leafs. Since a tree with just two leaves is a path, and a spanning path (that goes through all the nodes) is a Hamilton path, we can see how its possible to use an algorithm for the spanning tree eproblem to solve any Hamilton Path problem.

This proves that the spanning problem is NP-Hard. Since the problem is also clearly in NP, we thus can conclude that its NP complete.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1299