Hamiltonian path problem

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems 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 a finite constant 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 planar graphs.

Randomized algorithm

A randomized algorithm for Hamiltonian path that is fast on most graphs is the following: Start from a random vertex, and continue if there is a neighbor not visited. If there are no more unvisited neighbors, and the path formed isn't Hamiltonian, pick a neighbor uniformly at random, and rotate using that neighbor as a pivot. Then, continue the algorithm at the new end of the path.

See also

• Travelling salesman problem

External links

• Hamiltonian Page : Hamiltonian cycle and path problems, their generalizations and variations

References

• Rubin, Frank, " A Search Procedure for Hamilton Paths and Circuits'". Journal of the ACM, Volume 21, Issue 4. October 1974. ISSN 0004-5411
• M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete problems Proceedings of the sixth annual ACM symposium on Theory of computing, p.47-63. 1974.
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A1.3: GT37–39, pp.199–200.