1
$\begingroup$

So first of all I know finding MST is in P and is not NP complete. But I checked last year exams from my University and there is a problem: Given that Minimum Spanning Tree is NP-complete show that Hamiltonian Cycle is NP complete.

So I guess it is an assumption.

Is it just to say that if we find Hamiltonian cycle we can remove an edge with the heaviest weight and we get MST? But this is not a case because Hamiltonian cycle does not give us least weight edges.. This probably could be done with Traveling Salesmen Problem though.

Anyway, any ideas?

$\endgroup$
1
$\begingroup$

We know that MST $\in P$. If MST $ \in NPC$, then by definition of $NPC$ it means that every language in $NP$ is polynomially reducible to MST. But then, since MST $\in P$, every problem in $NP$ is in $P$. Thus, we can reduce any language $L$ in $NP$ to any other language $L'$ that has at least one member $X'_t \in L'$ and one member $X'_f \not \in L'$ as follows: compute whether $X \in L$ in polynomial time (since $L \in NP \in P$). Then, if $X \in L$, reduce it to $X'_t$. Otherwise, reduce it to $X'_f$.

$\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.