Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
Can you elaborate why you think the one version can be solved in polynomial time? –  Raphael Mar 27 '12 at 7:08
    
@pad: "My instructor asked in class" is not an assignment but a puzzle. Also, see this meta discussion on the homework tag. –  Raphael Mar 27 '12 at 7:09
add comment

1 Answer 1

up vote 10 down vote accepted

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]

share|improve this answer
    
Good to see you over here! Note that we have MathJax here, too. –  Raphael Mar 27 '12 at 14:12
1  
Thanks for the guidance!! I wish I read this before I went to class though, he spoiled it today haha. In case anyone interested the superset version polynomial algorithm, another hint is constructing a new graph with V\L. –  initialize Mar 27 '12 at 21:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.