Editing Hamiltonian path problem (section)

{{short description|Problem of finding a cycle through all vertices of a graph}}
{{about|the specific problem of determining whether a Hamiltonian path or cycle exists in a given graph|the general graph theory concepts|Hamiltonian path}}

The '''Hamiltonian path problem''' is a topic discussed in the fields of [[Computational complexity theory|complexity theory]] and [[graph theory]]. It decides if a [[Directed graph|directed]] or [[Undirected graph|undirected]] [[Graph (discrete mathematics)|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.<ref name=":12">{{Cite book |last=Sipser |first=Michael |title=Introduction to the Theory of Computation |publisher=Cengage Learning |year=2013 |edition=3rd |pages=292–314}}</ref>

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-completeness|NP-complete]] problems, as shown in [[Michael Garey]] and [[David S. Johnson|David S. Johnson's]] book [[Computers and Intractability|Computers and Intractability: A Guide to the Theory of NP-Completeness]] and [[Richard M. Karp|Richard Karp's]] list of [[Karp's 21 NP-complete problems|21 NP-complete problems]].<ref>{{Cite book |last1=Garey |first1=Michael R |title=Computers and Intractability: A Guide to the Theory of NP-Completeness |last2=Johnson |first2=David S. |publisher=W. H. Freeman and Company |year=1979 |pages=60}}</ref><ref name="Held 1965 136–147">{{Cite journal |last1=Held |first1=M. |last2=Karp |first2=R. M. |date=1965 |title=The construction of discrete dynamic programming algorithms |url=http://dx.doi.org/10.1147/sj.42.0136 |journal=IBM Systems Journal |volume=4 |issue=2 |pages=136–147 |doi=10.1147/sj.42.0136 |issn=0018-8670}}</ref>