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]

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

1 Answer 1

Reset to default
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.

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

Your Answer

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

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