NP completeness proof of a spanning tree problem

Problem Detail: 

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.

Asked By : initialize

Answered By : Tsuyoshi Ito

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]

Best Answer from StackOverflow

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