Editing Hamiltonian path problem (section)

==Algorithms==

=== Brute force ===
To decide if a graph has a Hamiltonian path, one would have to check each possible path in the input graph G. There are ''n''! different sequences of vertices that ''might'' be Hamiltonian paths in a given ''n''-vertex graph (and are, in a [[complete graph]]), so a [[brute force search]] algorithm that tests all possible sequences would be very slow.

=== Partial paths ===
An early exact algorithm for finding a Hamiltonian cycle on a directed graph was the enumerative algorithm of Martello.<ref name="Held 1965 136–147"/> A search procedure by Frank Rubin<ref>{{citation |last=Rubin |first=Frank |title=A Search Procedure for Hamilton Paths and Circuits |journal=[[Journal of the ACM]] |volume=21 |issue=4 |pages=576–80 |year=1974 |doi=10.1145/321850.321854 |s2cid=7132716|doi-access=free }}</ref> 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.

=== Dynamic programming ===
Also, a [[dynamic programming]] algorithm of [[Held-Karp algorithm|Bellman, Held, and Karp]] can be used to solve the problem in time O(''n''<sup>2</sup> 2<sup>''n''</sup>). In this method, one determines, for each set ''S'' of vertices and each vertex ''v'' in ''S'', whether there is a path that covers exactly the vertices in ''S'' and ends at ''v''. For each choice of ''S'' and ''v'', a path exists for (''S'',''v'') if and only if ''v'' has a neighbor ''w'' such that a path exists for (''S'' − ''v'',''w''), which can be looked up from already-computed information in the dynamic program.<ref>{{Cite journal |last=Bellman |first=Richard |date=January 1962 |title=Dynamic Programming Treatment of the Travelling Salesman Problem |journal=Journal of the ACM |language=en |volume=9 |issue=1 |pages=61–63 |doi=10.1145/321105.321111 |s2cid=15649582 |issn=0004-5411|doi-access=free }}</ref><ref>{{Cite journal |last1=Held |first1=Michael |last2=Karp |first2=Richard M. |date=March 1962 |title=A Dynamic Programming Approach to Sequencing Problems |url=http://epubs.siam.org/doi/10.1137/0110015 |journal=Journal of the Society for Industrial and Applied Mathematics |language=en |volume=10 |issue=1 |pages=196–210 |doi=10.1137/0110015 |issn=0368-4245}}</ref>

=== Monte Carlo ===
Andreas Björklund provided an alternative approach using the [[inclusion–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 arbitrary ''n''-vertex graphs by a [[Monte Carlo algorithm]] in time O(1.657<sup>''n''</sup>); for [[bipartite graph]]s this algorithm can be further improved to time [[Big O notation#Little-o notation|O]](1.415<sup>''n''</sup>).<ref>{{Cite book |last=Bjorklund |first=Andreas |title=2010 IEEE 51st Annual Symposium on Foundations of Computer Science |chapter=Determinant Sums for Undirected Hamiltonicity |date=October 2010 |chapter-url=http://dx.doi.org/10.1109/focs.2010.24 |pages=173–182 |publisher=IEEE |doi=10.1109/focs.2010.24|arxiv=1008.0541 |isbn=978-1-4244-8525-3 }}</ref>

=== Backtracking ===
For graphs of maximum degree three, a careful backtracking search can find a Hamiltonian cycle (if one exists) in time O(1.251<sup>''n''</sup>).<ref>{{Citation |last1=Iwama |first1=Kazuo |title=An Improved Exact Algorithm for Cubic Graph TSP |date=2007 |url=http://link.springer.com/10.1007/978-3-540-73545-8_13 |work=Computing and Combinatorics |volume=4598 |pages=108–117 |editor-last=Lin |editor-first=Guohui |access-date=2023-10-07 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |language=en |doi=10.1007/978-3-540-73545-8_13 |isbn=978-3-540-73544-1 |last2=Nakashima |first2=Takuya|series=Lecture Notes in Computer Science }}</ref>

=== Boolean satisfiability ===
Hamiltonian paths can be found using a [[SAT solver]]. The Hamiltonian path is NP-Complete meaning it can be [[Mapping reducibility|mapping reduced]] to the [[3-SAT|3-SAT problem]]. As a result, finding a solution to the Hamiltonian Path problem is equivalent to finding a solution for 3-SAT.

=== Unconventional methods ===
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 a [[DNA computing|DNA 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.<ref>{{citation |last=Adleman |first=Leonard |title=Molecular computation of solutions to combinatorial problems |date=November 1994 |journal=[[Science (journal)|Science]] |volume=266 |issue=5187 |pages=1021–1024 |bibcode=1994Sci...266.1021A |citeseerx=10.1.1.54.2565 |doi=10.1126/science.7973651 |jstor=2885489 |pmid=7973651 |author-link=Leonard Adleman}}.</ref>

An optical solution to the Hamiltonian problem has been proposed as well.<ref name="oltean_hamiltonian2">{{cite conference |author=Mihai Oltean |date=2006 |title=A light-based device for solving the Hamiltonian path problem |conference=Unconventional Computing |publisher=Springer LNCS 4135 |pages=217–227 |arxiv=0708.1496 |doi=10.1007/11839132_18}}</ref> 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.