Hamiltonian path problem
Encyclopedia
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 graph
s and the undirected Hamiltonian cycle problem remains NP-complete for cubic
planar graphs.
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.
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.
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).
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 quaternion
s (also invented by Hamilton). This the Icosian Calculus
solution is absent generalization to arbitrary graphs.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path
Hamiltonian path
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle in an undirected graph that visits each vertex exactly once and also returns to the starting vertex...
or a Hamiltonian cycle exists in a given graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
(whether directed
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
or undirected). Both problems are NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
. The problem of finding a Hamiltonian cycle or path is in FNP
FNP (complexity)
In computational complexity theory, the complexity class FNP is the function problem extension of the decision problem class NP. The name is somewhat of a misnomer, since technically it is a class of binary relations, not functions, as the following formal definition explains:This definition does...
.
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
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
, 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
Karp's 21 NP-complete problems
One of the most important results in computational complexity theory was Stephen Cook's 1971 demonstration of the first NP-complete problem, the boolean satisfiability problem...
. Garey and Johnson showed shortly afterwards in 1974 that the directed Hamiltonian cycle problem remains NP-complete for planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s and the undirected Hamiltonian cycle problem remains NP-complete for cubic
Cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
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
Leonard Adleman
Leonard Max Adleman is an American theoretical computer scientist and professor of computer science and molecular biology at the University of Southern California. He is known for being a co-inventor of the RSA cryptosystem in 1977, and of DNA computing...
published his work on solving a 7-vertex instance of the Hamiltonian Path Problem using a DNA computer
DNA computing
DNA computing is a form of computing which uses DNA, biochemistry and molecular biology, instead of the traditional silicon-based computer technologies. DNA computing, or, more generally, biomolecular computing, is a fast developing interdisciplinary area...
. 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.
In July 2009, research published in the Journal of Biological Engineering showed that a bacterial computer
DNA computing
DNA computing is a form of computing which uses DNA, biochemistry and molecular biology, instead of the traditional silicon-based computer technologies. DNA computing, or, more generally, biomolecular computing, is a fast developing interdisciplinary area...
can be used to solve a simple Hamiltonian path problem (using three locations).
Hamiltonian paths and cycles are named after William Rowan Hamilton
William Rowan Hamilton
Sir William Rowan Hamilton was an Irish physicist, astronomer, and mathematician, who made important contributions to classical mechanics, optics, and algebra. His studies of mechanical and optical systems led him to discover new mathematical concepts and techniques...
who invented the Icosian game
Icosian game
The icosian game is a mathematical game invented in 1857 by William Rowan Hamilton. The game's object is finding a Hamiltonian cycle along the edges of a dodecahedron such that every vertex is visited a single time, no edge is visited twice, and the ending point is the same as the starting point...
, 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
Icosian Calculus
The Icosian Calculus is a non-commutative algebraic structure discovered by the Irish mathematician William Rowan Hamilton in 1856.In modern terms, he gave a group presentation of the icosahedral rotation group by generators and relations....
, an algebraic structure
Algebraic structure
In abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...
based on roots of unity
Root of unity
In mathematics, a root of unity, or de Moivre number, is any complex number that equals 1 when raised to some integer power n. Roots of unity are used in many branches of mathematics, and are especially important in number theory, the theory of group characters, field theory, and the discrete...
with many similarities to the quaternion
Quaternion
In mathematics, the quaternions are a number system that extends the complex numbers. They were first described by Irish mathematician Sir William Rowan Hamilton in 1843 and applied to mechanics in three-dimensional space...
s (also invented by Hamilton). This the Icosian Calculus
Icosian Calculus
The Icosian Calculus is a non-commutative algebraic structure discovered by the Irish mathematician William Rowan Hamilton in 1856.In modern terms, he gave a group presentation of the icosahedral rotation group by generators and relations....
solution is absent generalization to arbitrary graphs.