HAM is NP-complete. First, we'll show that deciding if a directed graph has a Hamiltonian circuit is NP-hard. We'll reduce 3-CNF-SAT to it.
Idea: We have a widget for each clause and an assignment-selection gadget that makes us choose Boolean values for each of the variables one at a time. We have the option of satisfying a clause and returning to variable selection. We must satisfy all clauses and then complete the loop.
Picture...
x v with loop o--->o x -> x -> x -> y -> y -> y ... \ o \->o not x
Now, we can turn any undirected instance into a directed instance by expanding each node into a trio of nodes: for incoming edges, outgoing edges, and a middle node to force us to go from in to out. Why do we need the middle node?
Picture...
