Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Hamiltonian path problem
open-in-new
<p>The Hamiltonian path problem is a topic discussed in the fields of <a href="/facts/Computational_complexity_theory/etHuVF3U">complexity theory</a> and <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>. It decides if a <a href="/facts/Directed_graph/YBdfQ0um">directed</a> or <a href="/facts/Undirected_graph/kw3eIBUe">undirected</a> <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a>, <i>G</i>, contains a <a href="/facts/Hamiltonian_path/MHjY2xoY">Hamiltonian path</a>, 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 <i>s</i> and ending vertex <i>t</i> must be identified. </p><p>The Hamiltonian cycle problem is similar to the Hamiltonian path problem, except it asks if a given graph contains a <a href="/facts/Hamiltonian_cycle/MHjY2xoY">Hamiltonian cycle</a>. This problem may also specify the start of the cycle. The Hamiltonian cycle problem is a special case of the <a href="/facts/Travelling_salesman_problem/2WEKVLnV">travelling salesman problem</a>, 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 <i>n.</i> If so, the route is a Hamiltonian cycle. </p><p>The Hamiltonian path problem and the Hamiltonian cycle problem belong to the class of <a href="/facts/NP-completeness/NFPv56DU">NP-complete</a> problems, as shown in <a href="/facts/Michael_Garey/xuSLYs90">Michael Garey</a> and <a href="/facts/David_S._Johnson/kGSBxucb">David S. Johnson's</a> book <a href="/facts/Computers_and_Intractability/04FE56Ss">Computers and Intractability: A Guide to the Theory of NP-Completeness</a> and <a href="/facts/Richard_M._Karp/XtYCL0nA">Richard Karp's</a> list of <a href="/facts/Karp%27s_21_NP-complete_problems/dqu5bBh0">21 NP-complete problems</a>. </p>