I was reviewing some NP-complete problems on this site, and I meet one interesting problem from

NP completeness proof of a spanning tree problem

In this problem, I am interested in the original problem, which the leaf set is precisely $S$. The author said that he can prove this by reducing it to the Hamiltonian path. However, I still cannot figure it out. Could anybody help me with this in details?

  • 6
    $\begingroup$ Hint: What can you say about a tree with only two leaves? What if it's a spanning tree? $\endgroup$ – JeffE Apr 16 '12 at 8:36
  • 2
    $\begingroup$ Welcome! What have you tried? $\endgroup$ – Raphael Apr 16 '12 at 18:57
  • $\begingroup$ Thank you! I know that the H-path is a kind of spanning tree, and with this fact, I almost done. But, for the remain part, I don't know how to make a correspondence of the H-path problem to this problem, to make the leaves exactly $S$. I mean "leaves are precisely in $S$" is too tricky for me to create a correspondence...Thank you! $\endgroup$ – breezeintopl Apr 19 '12 at 19:45

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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