2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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, 2012 at 8:36
  • 2
    $\begingroup$ Welcome! What have you tried? $\endgroup$
    – Raphael ♦
    Apr 16, 2012 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, 2012 at 19:45

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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