1
$\begingroup$

I want to prove that the problem described here

Spanning tree with chosen leaves

is NP-Complete.

Of course it is in NP, but what problem would be appropriate to reduce to prove NP-Hardness? And how would that work?

$\endgroup$
  • $\begingroup$ This is my bad. I am fully aware. I am just a bit tired maybe because I am currently studying reductions, and I was so sure that this was an NP-complete problem, so I didn't even see the answers to the topic. :( Sorry for that! Your answer fully makes sense, thank you! $\endgroup$ – kopsti Feb 3 '16 at 2:39
  • $\begingroup$ Just a comment on terminology: you might end up with a spanning forest instead of a spanning tree if you designate a set of leaves. For example, just consider a path where some middle vertex is designated as a leaf. $\endgroup$ – G. Bach Feb 3 '16 at 9:34
3
$\begingroup$

The question you link to shows that the problem can be solved in polynomial time. If the problem was NP-complete, then this would prove that P = NP. Of course, it's a famous open problem to prove that P = NP or P != NP. Therefore, you shouldn't expect anyone to know of any such proof.

Also, many computer scientists expect P != NP; if they're right, then the problem you list is not NP-complete.

$\endgroup$

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.