Hi am reading https://www.cs.unm.edu/~saia/classes/362-s08/lec/lec24-2x2.pdf proving that the problem of checking if a graph has a hamiltonian cycle is NP-complete. It uses the fact that the problem of checking if a graph has a vertex cover of a given size is NP-complete, and it reduces the problem of vertex cover to the problem of Hamiltonian cycle (thus contradicting it not being NP-hard).
There are a few things I don't understand:
- I see there is a construction of the gadgets, but I don't understand what the big picture is: how do we obtain G' from G? How do we put the gadgets together?
- What is the motivation for this? I don't think I would have come up with anything like it on my own, and I'm trying to develop the skill of designing gadgets. I was trying to solve this on my own before I looked it up, but I didn't really get anywhere?