user26533291
Reputation: 1
Reduction from Hamiltonian Cycle to 3-SAT
I'm able to find many sources online describing the reduction from 3-SAT to Hamiltonian Cycle, which are both NP-complete problems. As such, I know that there must exist a reduction in the opposite direction, and I've been told that this has been defined, but I can't find it anywhere.
I tried searching the web rather thoroughly, but I don't have access to many textbooks/books on this subject so I'm reaching a dead end. Does anyone know if this reduction has actually been defined?
Upvotes: 0
Views: 116
Answers (0)
Related Questions
- Algorithm to return all combinations of k elements from n
- How can I pair socks from a pile efficiently?
- Expand a random range from 1–5 to 1–7
- "Check if a cycle of K nodes exists" reduction to SAT?
- Algorithms to find the number of Hamiltonian paths in a graph
- A way of reduction skyscrapper (latin square with height clues) to SAT
- hamiltonian cycle python wrong answer
- How to detect if the given graph has a cycle containing all of its nodes? Does the suggested algorithm have any flaws?
- Reduction algorithm from the Hamiltonian cycle