Hamiltonian path problem

Encyclopedia

In the mathematical

field of graph theory

the

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

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

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

, 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 pathHamiltonian 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 CalculusIcosian 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.