Hamiltonian path problem

This article is about the specific problem of determining whether a Hamiltonian path or cycle exists in a given graph. For the general graph theory concepts, see Hamiltonian path.

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 travelling 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.

Algorithms

A trivial heuristic algorithm for locating Hamiltonian paths is to construct a path abc... and extend it until no longer possible; when the path abc...xyz cannot be extended any longer because all neighbours of z already lie in the path, one goes back one step, removing the edge yz and extending the path with a different neighbour of y; if no choice produces a Hamiltonian path, then one takes a further step back, removing the edge xy and extending the path with a different neighbour of x, and so on. This algorithm will certainly find an Hamiltonian path (if any) but it runs in exponential time.

Some algorithms use a rotation argument as a fast way to get unstuck when a path that cannot be extended, transforming the path in a different path of the same length: given a path "abc...xyz" that cannot be extended because all neighbours of z lie on the path, one chooses some neighbour n of z and transforms the path "abc...n-op...xyz" into the path "abc...n-zyx...po"; the edge no is removed and replaced by the edge nz, while the subpath op...xyz is rotated.
This argument alone does not guarantee that a Hamiltonian path will eventually be found.

Solving the problem

Due to the complexity of the problem computers have to be used to solve what may seem to be minor tasks.

In November 1994, Leonard Adleman published his work on solving a 7-vertex instance of the Hamiltonian Path Problem using a DNA computer. Exploiting the parallelism inherent in chemical reactions, the problem is solvable with the number of required procedures growing linear in proportion to the number of vertices in the graph.^[1]

In July 2009, research published in the Journal of Biological Engineering showed that a bacterial computer can be used to solve a simple Hamiltonian path problem (using three locations).^[2]

Hamiltonian paths and cycles are named after William Rowan Hamilton who invented the Icosian game, now also known as Hamilton's puzzle, to find a Hamiltonian cycle in the edge graph of the dodecahedron. Hamilton solved this problem using the Icosian Calculus, an algebraic structure based on roots of unity with many similarities to the quaternions (also invented by Hamilton). This the Icosian Calculus solution is absent generalization to arbitrary graphs.

See also

• Travelling salesman problem
• Tait's conjecture

External links

References

1. ^ Adleman, Leonard (November). Science (American Association for the Advancement of Science) 266 (5187): 1021–1024. doi:10.1126/science.7973651. JSTOR 2885489. PMID 7973651. 
2. ^ [1]

• 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.