In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem is the problem of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph. Both problems are NP-complete. The problem of finding a Hamiltonian cycle or path is in FNP.

There is a simple relation between the two problems. The Hamiltonian path problem for graph G is equivalent to the Hamiltonian cycle problem in a graph H obtained from G by adding a new vertex and connecting it to all vertices of G.

The Hamiltonian cycle problem is a special case of the traveling salesman problem, obtained by setting the distance between two cities to unity if they are adjacent and infinity otherwise.

Quadratic algorithm for Dirac (dense) graphs

If the degree of every vertex is greater or equal than v/2, then the problem can be resolved in quadratic time. See [1] for details.

See also

• Traveling salesman problem

External links

• Hamiltonian cycle and path problems, their generalizations and variations

• Proof that Hamiltonian Cycle is NP-Complete

References

• Rubin, Frank, "A Search Procedure for Hamilton Paths and Circuits'". Journal of the ACM , Volume 21, Issue 4. October 1974. ISSN 0004-5411
• Nasu, Michiro, "A Study of Hamiltonian Circuit Problem". fourth draft, April 4, 1996 - August 18, 1999