NP completeness proof of a spanning tree problem I am looking for some hints in a question asked by my instructor.

So I just figured out this decision problem is $\sf{NP\text{-}complete}$:

In a graph $G$, is there a spanning tree in $G$ that contain an exact set of $S=\{x_1, x_2,\ldots, x_n\}$ as leafs. I figured out we can prove that it is $\sf{NP\text{-}complete}$ by reducing Hamiltonian path to this decisions problem.

But my instructor also asked us in class:


  would it also be $\sf{NP\text{-}complete}$ if instead of "exact set of $S$", we do 
  
  "include the whole set of $S$ and possibly other leafs" or 
     "subset of $S$"


I think "subset of S" would be $\sf{NP\text{-}complete}$, but I just can't prove it, I don't know what problem I can reduce it to this. As for "include the set of $S$..." I think it can be solved in polynomial time.
In short, your guesses are correct.  For the purpose of this answer, let’s call the three problems in question as follows:


Equality version: Given a graph $G = (V, E)$ and a set $S \subseteq V$, decide whether $G$ has a spanning tree $T$ such that the set of leaves in $T$ is equal to $S$.  As you stated, this is NP-complete by a reduction from the Hamiltonian path problem.
Subset version: Given $G$ and $S$ as above, decide whether $G$ has a spanning tree $T$ such that the set of leaves in $T$ is a subset of $S$.
Superset version: Given $G$ and $S$ as above, decide whether $G$ has a spanning tree $T$ such that the set of leaves in $T$ is a superset of $S$.


To prove that the subset version is NP-complete, you can still reduce the Hamitonian path problem to it.  Try to modify the proof of the NP-completeness of the equality version.

To prove that the superset version can be solved in polynomial time, try to find a necessary and sufficient condition for such a tree $T$ to exist.

Both versions (as well as some other problems about spanning trees) are studied in [SK05].  But I guess that it is better if you try to solve the problems by yourself before looking at the proofs in the paper, because looking at the paper can be a big spoiler.  Unfortunately I had looked at the paper before trying to find a polynomial-time algorithm for the superset version!



[SK05] Mohammad Sohel Rahman and Mohammad Kaykobad.  Complexities of some interesting problems on spanning trees.  Information Processing Letters, 94(2):93–97, April 2005.  [doi] [author copy]