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.

The Hamiltonian path problem is a topic discussed in the fields of complexity theory and graph theory. It decides if a directed or undirected graph, G, contains a Hamiltonian path, a path that visits every vertex in the graph exactly once. The problem may specify the start and end of the path, in which case the starting vertex s and ending vertex t must be identified.[1]

The Hamiltonian cycle problem is similar to the Hamiltonian path problem, except it asks if a given graph contains a Hamiltonian cycle. This problem may also specify the start of the cycle. The Hamiltonian cycle problem is a special case of the travelling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to n. If so, the route is a Hamiltonian cycle.

The Hamiltonian path problem and the Hamiltonian cycle problem belong to the class of NP-complete problems, as shown in Michael Garey and David S. Johnson's book Computers and Intractability: A Guide to the Theory of NP-Completeness and Richard Karp's list of 21 NP-complete problems.[2][3]

  1. ^ Sipser, Michael (2013). Introduction to the Theory of Computation (3rd ed.). Cengage Learning. pp. 292–314.
  2. ^ Garey, Michael R; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company. p. 60.
  3. ^ Held, M.; Karp, R. M. (1965). "The construction of discrete dynamic programming algorithms". IBM Systems Journal. 4 (2): 136–147. doi:10.1147/sj.42.0136. ISSN 0018-8670.