NP-completeness of a spanning tree problem
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.