I know that the Hamiltonian cycle problem in a directed/undirected graph is NP complete. The proofs I know rely on a reduction from 3-SAT. However, in these reductions the constructed graph is not simple (i.e., some pairs of nodes have multiple edges between them albeit with different orientations). I suspect that the problem remains NP-complete even if the attention is restricted to simple directed graphs (where there is at most one edge in between a pair of nodes). However, I wasn't able to find a reference.

Question: Is the Hamiltonian cycle problem still NP-complete when we focus on simple directed graphs?

  • $\begingroup$ A simple directed graph has no self-loops or multiple edges. Multiple edges in this case refers to edges with the same orientation. So, the constructed graph from your 3-SAT reduction is a simple directed graph. $\endgroup$ – user137481 Nov 28 '19 at 3:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.