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?
$\begingroup$
$\endgroup$
2
-
$\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$– kopstiFeb 3, 2016 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. BachFeb 3, 2016 at 9:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
