For homework I have the task

Assuming P ≠ NP, is the following set NP-complete:
{(G,w) | G is a Graph and w is a Hamilton cycle in G}

and I don't understand how to show that a set is NP-complete.

I know that generally one has to reduce the given problem to another NP-complete problem to show that is is NP-complete.

Or as a first step show that the problem is even in NP (one could do that showing that there is a certificate that shows a given solution is valid in polynomial time).
This is rather easy since checking if a given path is a Hamilton cycle in G is known to be done in polynomial time.


marked as duplicate by D.W. Jul 7 '18 at 18:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ The answer to the question in your title is at cs.stackexchange.com/q/9556/755. General strategies for how to prove a problem is NP-complete can be found at cs.stackexchange.com/q/11209/755 and cs.stackexchange.com/q/1240/755. This page has advice on how to use this site to help you with homework exercises. Note that we are a question-and-answer site, so we require you to articulate a specific question in the body of your post (a question about your exercise; not just a statement of the exercise). $\endgroup$ – D.W. Jul 7 '18 at 18:35