NP completeness proof of a spanning tree problem

ignougroup
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{NPtext{-}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{NPtext{-}complete}$ by reducing Hamiltonian path to this decisions problem. But my instructor also asked us in class:

would it also be $sf{NPtext{-}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{NPtext{-}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