Hamiltonian path problem

related topics
{math, number, function}
{line, north, south}
{city, population, household}

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.

Contents

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. (That is, add an edge to that neighbor, and remove one of the existing edges from that neighbor so as not to form a loop.) Then, continue the algorithm at the new end of the path.
As an example, take a graph with nodes ABCDE, and possible connections AD, DC, DE, CE, BC. Starting at A, we continue along AD. Randomly picking a vertex, we choose C, and the path so far is A-D-C. Again, picking a vertex, we may come to E, giving path A-D-C-E. Here there are no free neighbours, but we have not yet visited B so the path is not Hamiltonian. Therefore, we pick a neighbour to E (our ending point at the moment) - this can be C or D. If we pick D as the pivot, then we add DE to the path. This gives us a loop CDE, so we remove CD, leaving a path A-D-E-C (note that the previous end-point, E, is now in the middle). The algorithm continues; we choose B as the only neighbour left; there are no remaining neighbours, the path is Hamiltonian so the algorithm terminates.

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 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).[1]

See also

Full article ▸

related documents
Characteristic subgroup
Mutual recursion
Complete category
Category of sets
Elias delta coding
Baire category theorem
Product of rings
Abelian category
Brun's constant
Sophie Germain prime
Column vector
Sum rule in differentiation
Axiom of union
Zero divisor
Normal morphism
RP (complexity)
Endomorphism
Double precision
AVL tree
Up to
Blum Blum Shub
Contraction mapping
Complete measure
Nearest neighbour algorithm
Inverse functions and differentiation
LALR parser
Sharp-P
Identifier
Best-first search
Inequation