0
$\begingroup$

Recently, I studied how to prove a problem is NP-complete. From the book Introduction to Algorithms (CLRS, 3rd edition), there is an example of reducing vertex cover to Hamiltonian cycle. I believe that it is possible to directly reduce clique to Hamiltonian cycle in an undirected graph, but how to convert it in polynomial time?

[Deleted question]

$\endgroup$
7
  • $\begingroup$ Please do not delete and reask a question when you have received a (partially) useful answer. $\endgroup$
    – Discrete lizard
    Nov 25 at 20:37
  • $\begingroup$ @Discretelizard No, the answer is correct only if the graph is directed. $\endgroup$ Nov 25 at 20:45
  • $\begingroup$ @Discretelizard I request for undeleting the question I posted, or delete the answer of this question. $\endgroup$ Nov 25 at 20:45
  • $\begingroup$ @Discretelizard He just gave an answer and left, but my problem hasn't been solved. $\endgroup$ Nov 25 at 20:50
  • $\begingroup$ @Discretelizard I quit. $\endgroup$ Nov 26 at 14:53
1
$\begingroup$

You can reduce clique to SAT (Cook's theorem). You can reduce SAT to Hamiltonian cycle (see e.g. Easy reduction from 3SAT to Hamiltonian path problem for the main ideas). Compose these two, and you get a reduction from clique to Hamiltonian cycle.

$\endgroup$
2
  • $\begingroup$ How to solve it if the graph is undirected? $\endgroup$ Nov 24 at 19:16
  • $\begingroup$ You cannot always assume it is directed by default(the easiest case). $\endgroup$ Nov 26 at 14:52

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.