Hamiltonian path problem

From Free net 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 traveling salesman problem, obtained by setting the distance between two cities to unity 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 1 Quadratic algorithm for Dirac (dense) graphs 2 Randomized Algorithm 3 See also 4 External links 5 References

Quadratic algorithm for Dirac (dense) graphs

If the degree of every vertex is greater than or equal to v/2, then the problem can be resolved in quadratic time. See [1] for details.

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

• Traveling salesman problem

External links

• Hamiltonian Page : Hamiltonian cycle and path problems, their generalizations and variations
• Proof that the Hamiltonian Cycle problem is NP-complete by reduction from 3-SAT

References

• Rubin, Frank, "A Search Procedure for Hamilton Paths and Circuits'". Journal of the ACM, Volume 21, Issue 4. October 1974. ISSN 0004-5411
• Nasu, Michiro, "A Study of Hamiltonian Circuit Problem". fourth draft, April 4, 1996 - August 18, 1999
• 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.
• Template:Cite book A1.3: GT37–39, pp.199–200.de:Hamiltonkreisproblem