TheHamiltonian path problem is a topic discussed in the fields ofcomplexity theory andgraph theory. It decides if adirected orundirectedgraph,G, contains aHamiltonian 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 vertexs and ending vertext must be identified.^[1]

TheHamiltonian cycle problem is similar to the Hamiltonian path problem, except it asks if a given graph contains aHamiltonian cycle. This problem may also specify the start of the cycle. The Hamiltonian cycle problem is a special case of thetravelling 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 ton. If so, the route is a Hamiltonian cycle.

The Hamiltonian path problem and the Hamiltonian cycle problem belong to the class ofNP-complete problems, as shown inMichael Garey andDavid S. Johnson's bookComputers and Intractability: A Guide to the Theory of NP-Completeness andRichard Karp's list of21 NP-complete problems.^[2][3]

The problems of finding a Hamiltonian path and a Hamiltonian cycle can be related as follows:

• In one direction, the Hamiltonian path problem for graphG can be related to the Hamiltonian cycle problem in a graphH obtained fromG by adding a newuniversal vertexx, connectingx to all vertices ofG. Thus, finding a Hamiltonian path cannot be significantly slower (in the worst case, as a function of the number of vertices) than finding a Hamiltonian cycle.
• In the other direction, the Hamiltonian cycle problem for a graphG is equivalent to the Hamiltonian path problem in the graphH obtained by adding terminal (degree-one) verticess andt attached respectively to a vertex v of G and tov', acleaved copy ofv which givesv'the same neighbourhood asv. The Hamiltonian path inH running through vertices⁠${\displaystyle s-v-x-\cdots -y-v^{\prime }-t}$⁠ corresponds to the Hamiltonian cycle inG running through⁠${\displaystyle v-x-\cdots -y(-v)}$⁠.^[4]

To decide if a graph has a Hamiltonian path, one would have to check each possible path in the input graph G. There aren! different sequences of vertices thatmight be Hamiltonian paths in a givenn-vertex graph (and are, in acomplete graph), so abrute force search algorithm that tests all possible sequences would be very slow.

An early exact algorithm for finding a Hamiltonian cycle on a directed graph was the enumerative algorithm of Martello.^[3] A search procedure by Frank Rubin^[5] divides the edges of the graph into three classes: those that must be in the path, those that cannot be in the path, and undecided. As the search proceeds, a set of decision rules classifies the undecided edges, and determines whether to halt or continue the search. Edges that cannot be in the path can be eliminated, so the search gets continually smaller. The algorithm also divides the graph into components that can be solved separately, greatly reducing the search size. In practice, this algorithm is still the fastest.

Also, adynamic programming algorithm ofBellman, Held, and Karp can be used to solve the problem in time O(n² 2ⁿ). In this method, one determines, for each setS of vertices and each vertexv inS, whether there is a path that covers exactly the vertices inS and ends atv. For each choice ofS andv, a path exists for (S,v) if and only ifv has a neighborw such that a path exists for (S −v,w), which can be looked up from already-computed information in the dynamic program.^[6][7]

Andreas Björklund provided an alternative approach using theinclusion–exclusion principle to reduce the problem of counting the number of Hamiltonian cycles to a simpler counting problem, of counting cycle covers, which can be solved by computing certain matrix determinants. Using this method, he showed how to solve the Hamiltonian cycle problem in arbitraryn-vertex graphs by aMonte Carlo algorithm in time O(1.657ⁿ); forbipartite graphs this algorithm can be further improved to timeO(1.415ⁿ).^[8]

For graphs of maximum degree three, a careful backtracking search can find a Hamiltonian cycle (if one exists) in time O(1.251ⁿ).^[9]

Hamiltonian paths can be found using aSAT solver. The Hamiltonian path is NP-Complete meaning it can bemapping reduced to the3-SAT problem. As a result, finding a solution to the Hamiltonian Path problem is equivalent to finding a solution for 3-SAT.

Because of the difficulty of solving the Hamiltonian path and cycle problems on conventional computers, they have also been studied in unconventional models of computing. For instance,Leonard Adleman showed that the Hamiltonian path problem may be solved using aDNA computer. Exploiting the parallelism inherent in chemical reactions, the problem may be solved using a number of chemical reaction steps linear in the number of vertices of the graph; however, it requires a factorial number of DNA molecules to participate in the reaction.^[10]

An optical solution to the Hamiltonian problem has been proposed as well.^[11] The idea is to create a graph-like structure made from optical cables and beam splitters which are traversed by light in order to construct a solution for the problem. The weak point of this approach is the required amount of energy which is exponential in the number of nodes.

The problem of finding a Hamiltonian cycle or path is inFNP; the analogousdecision problem is to test whether a Hamiltonian cycle or path exists. The directed and undirected Hamiltonian cycle problems were two ofKarp's 21 NP-complete problems. They remain NP-complete even for special kinds of graphs, such as:

• bipartite graphs,^[12]
• undirectedplanar graphs of maximum degree three,^[13]
• directed planar graphs with indegree and outdegree at most two,^[14]
• bridgeless undirected planar 3-regularbipartite graphs,
• 3-connected 3-regular bipartite graphs,^[15]
• subgraphs of thesquare grid graph,^[16]
• cubic subgraphs of the square grid graph.^[17]

However, for some special classes of graphs, the problem can be solved in polynomial time:

• 4-connected planar graphs are always Hamiltonian by a result due toTutte, and the computational task of finding a Hamiltonian cycle in these graphs can be carried out in linear time^[18] by computing a so-calledTutte path.
• Tutte proved this result by showing that every 2-connected planar graph contains a Tutte path. Tutte paths in turn can be computed in quadratic time even for 2-connected planar graphs,^[19] which may be used to find Hamiltonian cycles and long cycles in generalizations of planar graphs.

Putting all of these conditions together, it remains open whether 3-connected 3-regular bipartite planar graphs must always contain a Hamiltonian cycle, in which case the problem restricted to those graphs could not be NP-complete; seeBarnette's conjecture.

In graphs in which all vertices have odd degree, an argument related to thehandshaking lemma shows that the number of Hamiltonian cycles through any fixed edge is always even, so if one Hamiltonian cycle is given, then a second one must also exist.^[20] However, finding this second cycle does not seem to be an easy computational task.Papadimitriou defined thecomplexity classPPA to encapsulate problems such as this one.^[21]

The Hamiltonian path problem is NP meaning a proposed solution can be verified inpolynomial time.^[1]

A verifieralgorithm for Hamiltonian path will take as input a graph G, starting vertex s, and ending vertex t. Additionally, verifiers require a potential solution known as acertificate, c. For the Hamiltonian Path problem, c would consist of astring of vertices where the first vertex is the start of the proposed path and the last is the end.^[22] The algorithm will determine if c is a validHamiltonian Path in G and if so, accept.

To decide this, the algorithm first verifies that all of the vertices in G appear exactly once in c. If this check passes, next, the algorithm will ensure that the first vertex in c is equal to s and the last vertex is equal to t. Lastly, to verify that c is a valid path, the algorithm must check that every edge between vertices in c is indeed an edge in G. If any of these checks fail, the algorithm will reject. Otherwise, it will accept.^[22][23]

The algorithm can check in polynomial time if the vertices in G appear once in c. Additionally, it takes polynomial time to check the start and end vertices, as well as the edges between vertices. Therefore, the algorithm is a polynomial time verifier for the Hamiltonian path problem.^[22]

Networks on chip (NoC) are used in computer systems andprocessors serving as communication for on-chip components.^[24] The performance of NoC is determined by the method it uses to movepackets of data across anetwork.^[25] The Hamiltonian Path problem can be implemented as a path-based method inmulticast routing. Path-based multicast algorithms will determine if there is a Hamiltonian path from the startnode to each end node and send packets across the corresponding path. Utilizing this strategy guaranteesdeadlock andlivelock free routing, increasing the efficiency of the NoC.^[26]

Rendering engines are a form ofsoftware used incomputer graphics to generate images or models from input data.^[27] Inthree dimensional graphics rendering, a common input to the engine is apolygon mesh. The time it takes to render the object is dependent on the rate at which the input is received, meaning the larger the input the longer the rendering time. For triangle meshes, however, the rendering time can be decreased by up to a factor of three. This is done through "ordering the triangles so that consecutive triangles share a face."^[28] That way, only one vertex changes between each consecutive triangle. This ordering exists if thedual graph of the triangular mesh contains a Hamiltonian path.

Media related toHamiltonian path problem at Wikimedia Commons

• NP-complete problems
• Computational problems in graph theory
• Hamiltonian paths and cycles

• CS1 maint: work parameter with ISBN
• Articles with short description
• Short description is different from Wikidata
• Commons category link from Wikidata