# Hamiltonian path problem

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 (whether directed or undirected). 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.

The directed and undirected Hamiltonian cycle problems were two of Karp's 21 NP-complete problems. Garey and Johnson showed shortly afterwards in 1974 that the directed Hamiltonian cycle problem remains NP-complete for planar graphs and the undirected Hamiltonian cycle problem remains NP-complete for cubic graphs.

 Contents

## 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] (http://cgm.cs.mcgill.ca/~perouz/cs251/documents/solutions6/solutions6.html) for details.

## References

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy