While the general problem of detecting a Hamiltonian path or cycle on an undirected grid graph is known to be NP-complete, are there interesting special cases where efficient polynomial time algorithms exist for enumerating all such paths/cycles? Perhaps for certain kinds of k-ary n-cube graphs? I hope this question isn't too open-ended…
Update – Is the problem of iterating Hamiltonian path/circuits known to be NP-complete for the N-cube?
Best Answer
There are certainly special graphs that are always Hamiltonian (if every vertex of a graph of n vertices has degree at least n/2, say) and these have efficient algorithms associated with them.
For instance, this paper proves the graph of a random 5-outregular digraph is Hamiltonian and there is an algorithm that finds a Hamiltonian cycle in polynomial time.