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.

Contents

1 Quadratic algorithm for Dirac (dense) graphs 2 See also 3 External links 4 References

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