Directed Hamiltonian Circuit

Input

Directed graph $G = (V, A)$.

Question

Does $G$ contain a directed Hamiltonian circuit?

Classes

• NP-complete

Comments

Remains NP-complete if $G$ is planar and has no vertex involved in more than three arcs (Plesnik, 1979). Solvable in polynomial time if no in-degree (no out-degree) exceeds 1, if $G$ is a tournament (Morrow & Goodman, 1976), or if $G$ is an edge digraph (e.g., see (Liu, 1968)).

Proofs

NP-complete

Transformation from Vertex Cover (Karp, 1972).

Reducible from

• Vertex Cover

Reducible to

• Minimum Equivalent Digraph

References

• Plesnik, J. (1979). The np-completeness of the hamiltonian cycle problem in planar diagraphs with degree bound two. Information Processing Letters, 8(4), 199–201. https://doi.org/10.1016/0020-0190(79)90023-1
• Morrow, C., & Goodman, S. (1976). An efficient algorithm for finding a longest cycle in a tournament. Proc. 7th Southeastern Conference on Combinatorics, Graph Theory, and Computing, 453–462.
• Liu, C. L. (1968). Introduction to combinatorial mathematics. McGraw-Hill.
• Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85–103). Springer US. https://doi.org/10.1007/978-1-4684-2001-2_9