Hamiltonian Circuit

Input

Graph $G = (V, E)$.

Question

Does $G$ contain a Hamiltonian circuit?

Classes

• NP-complete

Comments

Remains NP-complete (1) if $G$ is planar, cubic, 3-connected, and has no face with fewer than 5 edges (Garey et al., 1976), (2) if $G$ is bipartite (Krishnamoorthy, 1975), (3) if $G$ is the square of a graph, and (4) if a Hamiltonian path for $G$ is given as part of the instance (Papadimitriou & Steiglitz, 1976). Solvable in polynomial time if $G$ has no vertex with degree exceeding 2 or if $G$ is an edge graph (e.g. see (Liu, 1968)). The cube of a non-trivial connected graph always has a Hamiltonian circuit (Karaganis, 1968).

Proofs

NP-complete

Transformation from Vertex Cover (Karp, 1972).

Reducible from

• Vertex Cover

Reducible to

• Traveling Salesman

References

• Garey, M. R., Johnson, D. S., & Tarjan, R. E. (1976). The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM Journal on Computing, 5(4), 704–714. https://doi.org/10.1137/0205049
• Krishnamoorthy, M. S. (1975). An NP-hard problem in bipartite graphs. ACM SIGACT News, 7(1), 26–26. https://doi.org/10.1145/990518.990521
• Papadimitriou, C. H., & Steiglitz, K. (1976). Some complexity results for the Traveling Salesman Problem. Proceedings of the Eighth Annual ACM Symposium on Theory of Computing - STOC ’76. https://doi.org/10.1145/800113.803625
• Liu, C. L. (1968). Introduction to combinatorial mathematics. McGraw-Hill.
• Karaganis, J. J. (1968). On the Cube of a Graph. Canadian Mathematical Bulletin, 11(2), 295–296. https://doi.org/10.4153/cmb-1968-037-0
• 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