Jump to content

Hamiltonian path problem: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
mNo edit summary
m correcting link after RM
 
(27 intermediate revisions by 20 users not shown)
Line 1: Line 1:
{{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}}
{{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>
In the [[mathematics|mathematical]] field of [[graph theory]] the '''Hamiltonian path problem''' and the '''Hamiltonian cycle problem''' are problems of determining whether a [[Hamiltonian path]] (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given [[Graph (discrete mathematics)|graph]] (whether [[directed graph|directed]] or [[undirected graph|undirected]]). Both problems are [[NP-complete]].<ref>{{Citation|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | isbn = 978-0-7167-1045-5| title-link = Computers and Intractability: A Guide to the Theory of NP-Completeness }} A1.3: GT37&ndash;39, pp.&nbsp;199&ndash;200.</ref>


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 circuit; if there is no Hamiltonian circuit then the shortest route will be longer).
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>
== Reduction between the path problem and the cycle problem ==
There is a simple relation between the problems of finding a Hamiltonian path and a Hamiltonian cycle:


== Reductions ==
* In one direction, the Hamiltonian path problem for graph G is equivalent to the Hamiltonian cycle problem in a graph H obtained from G by adding a new vertex ''x'' and connecting ''x'' to all vertices of G. 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 graph G is equivalent to the Hamiltonian path problem in the graph H obtained by copying one vertex v of G, v', that is, letting v' have the same neighbourhood as v, and by adding two dummy vertices of degree one, and connecting them with v and v', respectively.<ref>[https://math.stackexchange.com/q/1290804 Reduction from Hamiltonian cycle to Hamiltonian path]</ref>


=== Reduction from the path problem to the cycle problem ===
==Algorithms==
The problems of finding a Hamiltonian path and a Hamiltonian cycle can be related as follows:
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. An early exact algorithm for finding an Hamiltonian cycle on a directed graph was the enumerative algorithm of Martello<ref>{{citation
| last = Martello | first = Silvano
| journal = [[ACM Transactions on Mathematical Software]]
| pages = 131–138
| title = An Enumerative Algorithm for Finding Hamiltonian Circuits in a Directed Graph
| volume = 9
| year = 1983
| doi = 10.1145/356022.356030
| issue = 1}}</ref>. A search procedure by Frank Rubin<ref>{{citation
| last = Rubin | first = Frank
| journal = [[Journal of the ACM]]
| pages = 576–80
| title = A Search Procedure for Hamilton Paths and Circuits
| volume = 21
| year = 1974
| doi = 10.1145/321850.321854
| issue = 4}}.</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. The algorithm divides the graph into components that can be solved separately. Also, a [[dynamic programming]] algorithm of Bellman, Held, and Karp can be used to solve the problem in time O(''n''<sup>2</sup>&nbsp;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''&nbsp;&minus;&nbsp;''v'',''w''), which can be looked up from already-computed information in the dynamic program.<ref>{{citation
| last = Bellman | first = R. | authorlink = Richard Bellman
| doi = 10.1145/321105.321111
| journal = [[Journal of the ACM]]
| pages = 61–63
| title = Dynamic programming treatment of the travelling salesman problem
| volume = 9
| year = 1962}}.</ref><ref>{{citation
| last1 = Held | first1 = M.
| last2 = Karp | first2 = R. M. | author2-link = Richard Karp
| doi = 10.1137/0110015
| issue = 1
| journal = J. SIAM
| pages = 196–210
| title = A dynamic programming approach to sequencing problems
| volume = 10
| year = 1962| hdl = 10338.dmlcz/103900
}}.</ref>


* In one direction, the Hamiltonian path problem for graph ''G'' can be related to the Hamiltonian cycle problem in a graph ''H'' obtained from ''G'' by adding a new [[universal vertex]] ''x'', connecting ''x'' to all vertices of ''G''. 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.
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>{{citation
* In the other direction, the Hamiltonian cycle problem for a graph ''G'' is equivalent to the Hamiltonian path problem in the graph ''H'' obtained by adding terminal ([[degree (graph theory)|degree]]-one) vertices ''s'' and ''t'' attached respectively to a vertex v of G and to ''v','' a [[Edge contraction#Vertex cleaving|cleaved copy]] of ''v'' which gives ''v' ''the same neighbourhood as ''v''. The Hamiltonian path in ''H'' running through vertices {{tmath|s-v-x-\cdots-y-v'-t}} corresponds to the Hamiltonian cycle in ''G'' running through {{tmath|v-x-\cdots-y(-v)}}.<ref>[https://math.stackexchange.com/q/1290804 Reduction from Hamiltonian cycle to Hamiltonian path]</ref>
| last = Björklund | first = Andreas
| arxiv = 1008.0541
| contribution = Determinant sums for undirected Hamiltonicity
| doi = 10.1109/FOCS.2010.24
| pages = 173–182
| title = Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10)
| year = 2010
| isbn = 978-1-4244-8525-3}}.</ref>


==Algorithms==
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
| last2 = Nakashima | first2 = Takuya
| contribution = An improved exact algorithm for cubic graph TSP
| doi = 10.1007/978-3-540-73545-8_13
| pages = 108–117
| series = Lecture Notes in Computer Science
| title = Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007)
| volume = 4598
| year = 2007
| isbn = 978-3-540-73544-1| citeseerx = 10.1.1.219.1672
}}.</ref>

Hamiltonian paths and cycles can be found using a [[SAT solver]].

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

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

== The Hamiltonian cycle polynomial ==

An algebraic option sometimes useful for determining the existence of a Hamiltonian cycle in a directed graph is using the Hamiltonian cycle
polynomial of an ''n''×''n''-matrix <math>A</math> defined as <math> \operatorname{ham}(A)=\sum_{\sigma\in H_n}\prod_{i=1}^n a_{i,\sigma(i)}</math> where <math>{H_n}</math> is the set of n-permutations having exactly one cycle. It's a generalization of the number of Hamiltonian cycles of a digraph as the sum of the products of its Hamiltonian cycles' arc weights (all of whom equal unity) for weighted digraphs with arc weights taken from a given commutative ring. In the meantime, for an undirected weighted graph the sum of the products of the edge weights of its Hamiltonian cycles containing any fixed edge (i,j) can be expressed as the product of the weight of (i,j) and the Hamiltonian cycle polynomial of the matrix received from its weighted adjacency matrix via removing the i-th row and the j-th column.


=== Brute force ===
In ({{harvtxt|Knezevic|Cohen|2017}}) it was shown that <math>\operatorname{ham} (A) = \Sigma_{J\subseteq \{2,\dots,n\}} (-1)^{|J|}\det(A_J)\operatorname{per}(A_{\bar J})</math>
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.
where <math>A_J</math> is the submatrix of <math>A</math> induced by the rows and columns of <math>A</math>
indexed by <math>J</math>, and <math>\bar J</math> is the complement of <math>J</math> in <math>\{1,\dots,n\}</math>, while the determinant of the empty submatrix is defined to be 1. In a field of characteristic 2 the latter equality turns into <math>\operatorname{ham} (A) = \Sigma_{J\subseteq \{2,\dots,n\}} \det(A_J)\operatorname{det}(A_{\bar J})</math> what therefore provides an opportunity to polynomial-time calculate the Hamiltonian cycle polynomial of any unitary matrix <math>U</math> (i.e. such that <math>U^{T} U = I</math> where <math>I</math> is the identity ''n''×''n''-matrix), because in such a field each minor of a unitary matrix coincides with its algebraic complement: <math> \operatorname{ham} (U) = \operatorname{det}^2(U + I_{/1}) </math> where <math> I_{/1} </math> is the identity ''n''×''n''-matrix with the entry of indexes 1,1 replaced by 0. Hence if it's possible to assign weights from a field of characteristic 2 to a digraph's arcs that make its weighted adjacency matrix unitary and the Hamiltonian cycle polynomial of this matrix is non-zero then the digraph is Hamiltonian.


=== Partial paths ===
Besides, in an arbitrary ring <math>R</math> for any skew-symmetric ''n''×''n''-matrix <math>A</math> there exists a power series in a formal variable <math>\varepsilon</math>: <math> U(\varepsilon) =\sum_{n=0}^\infty U_n \varepsilon^n </math> such that it's a unitary ''n''×''n''-matrix over <math>R\left(\varepsilon\right)</math> and <math>U_0 = I</math>, <math>U_1 = A</math>, while for any <math> U(\varepsilon)</math> satisfying these conditions <math>\operatorname{ham} (A)</math> equals the coefficient at the <math>n</math>-th power of <math>\varepsilon</math> in the power series <math>\operatorname{ham} (U(\varepsilon))</math>. It implies that computing, up to the <math>n</math>-th power of <math>\varepsilon</math>, the Hamiltonian cycle polynomial of a unitary ''n''×''n''-matrix over the infinite extension of any ring of characteristic q (not necessarily prime) by the formal variable <math>\varepsilon</math> is a [[Sharp-P-complete|#q-P-complete]] problem if <math>q</math> isn't 2 and computing the Hamiltonian cycle polynomial of a <math>k</math>-semi-unitary matrix (i.e. an ''n''×''n''-matrix <math>V</math> such that <math>rank(V^{T} V - I \,) = k</math>) over such an extension of any ring of characteristic 2 is a [[Sharp-P-complete|#2-P-complete]] problem for any <math>k</math> > 0 (because any <math>k</math>-semi-unitary matrix can be received from a unitary matrix via removing <math>k</math> rows and <math>k</math> columns). For <math>k = 1</math> the latter statement can be re-formulated as the #2-P-completeness of computing, for a given unitary ''n''×''n''-matrix <math>U</math> over a field of characteristic 2, the ''n''×''n''-matrix <math>H(U)</math> whose i,j-th entry is the Hamiltonian cycle polynomial of the matrix received from <math>U</math> via removing its i-th row and j-th column. This matrix satisfies the following matrix equation: <math>U(H(U))^T = H(U)U^T</math>.
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 ===
Moreover, it would be worth noting that in characteristic 2 the Hamiltonian cycle polynomial possesses its invariant matrix compressions (partly analogical to the Gaussian modification that is invariant for the determinant), taking into account the fact that <math>\operatorname{ham} (X) = 0</math> for any ''t''×''t''-matrix <math>X</math> having three equal rows or, if <math>t</math> > 2, a pair of indexes i,j such that its i-th and j-th rows are identical and its i-th and j-th columns are identical too. Hence if a matrix has two equal rows then adding one of them to any third one doesn't change this polynomial in characteristic 2, and also it isn't changed by adding the i-th column to the j-th one in a matrix where the i-th and j-th rows are identical. These facts, particularly, yield in characteristic 2 the identity <math>\operatorname{det(D+D^{-1})ham \left ( \begin{matrix}V & A \\B & U \end{matrix} \right ) = ham \left ( \begin{matrix}V & V+D & A\\ V+D^{-1} & V+D^{-1}+D & A\\ B & B & U\end{matrix} \right )}</math> for an ''n''×''n''-matrix <math>U</math>, ''m''×''m''-matrices <math>V</math> and diagonal <math>D</math>, ''m''×''n''-matrix <math>A</math> and ''n''×''m''-matrix <math>B</math>.
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 ===
This identity's restriction to the case when <math>U</math> is unitary, <math> VD + DV^{T}+AA^{T}=I+D^{2} </math> and <math>BD=UA^{T}</math>, where <math>I</math> is the identity ''m''×''m''-matrix, makes the ''(2m+n)''×''(2m+n)''-matrix in the equality's right side unitary and its Hamiltonian cycle polynomial computable, hence, in polynomial time what therefore generalizes the above-given formula for the Hamiltonian cycle polynomial of a unitary matrix.
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 ===
Apart from the above-mentioned compression transformations, in characteristic 2 the following relation is also valid for the Hamiltonian cycle polynomials of a matrix and its partial inverse (for <math>A_{11}</math> and <math>A_{22}</math> being square, <math>A_{11}</math> being [[Invertible matrix|invertible]]):
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 ===
<math>\operatorname{ham\left ( \begin{matrix}A_{11} & A_{12}\\ A_{21} & A_{22}\end{matrix} \right) = det^{2}\left ( A_{11} \right )ham\left ( \begin{matrix}A_{11}^{-1} & A_{11}^{-1}A_{12}\\ A_{21}A_{11}^{-1} & A_{22} + A_{21}A_{11}^{-1}A_{12}\end{matrix} \right )}</math>
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 ===
and, due to the fact that the Hamiltonian cycle polynomial doesn't depend on the matrix's diagonal entris, adding an arbitrary diagonal matrix doesn't change this polynomial too. These two types of transformation don't compress the matrix, but keep its size unchanged. However, in a number of cases their application alows to reduce the matrix's size by some of the above-mentioned compression operators.
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>
Hence there is a variety of matrix compression operators performed in polynomial time and preserving the Hamiltonian cycle polynomial in characteristic 2 whose sequential application, together with the transposition transformation (utilized each time the operators leave the matrix intact) has, for each matrix, a certain limit that can be defined as the compression-closure operator. When applied to classes of matrices, that operator thus maps one class into another. As it was proven in ({{harvtxt|Knezevic|Cohen|2017}}), if the compression-closure operator maps the class of unitary matrices into all the set of square matrices over an infinite field of characteristic 2 then the Hamiltonian cycle polynomial is computable in polynomial time over any field of this characteristic what would imply the equality RP = NP.


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.


==Complexity==
==Complexity==
The problem of finding a Hamiltonian cycle or path is in [[FNP (complexity)|FNP]]; the analogous [[decision problem]] is to test whether a Hamiltonian cycle or path exists. The directed and undirected Hamiltonian cycle problems were two of [[Karp's 21 NP-complete problems]]. They remain NP-complete even for special kinds of graphs, such as:
The problem of finding a Hamiltonian cycle or path is in [[FNP (complexity)|FNP]]; the analogous [[decision problem]] is to test whether a Hamiltonian cycle or path exists. The directed and undirected Hamiltonian cycle problems were two of [[Karp's 21 NP-complete problems]]. They remain NP-complete even for special kinds of graphs, such as:


* [[Bipartite graph|bipartite graphs]],<ref>{{Cite web|url=https://cs.stackexchange.com/q/18335 |title=Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete|website=Computer Science Stack Exchange|access-date=2019-03-18}}</ref>
* [[bipartite graph]]s,<ref>{{Cite web|url=https://cs.stackexchange.com/q/18335 |title=Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete|website=Computer Science Stack Exchange|access-date=2019-03-18}}</ref>
* undirected [[planar graph]]s of maximum degree three,<ref>{{citation
* undirected [[planar graph]]s of maximum degree three,<ref>{{citation
| last1 = Garey | first1 = M. R. | author1-link = Michael Garey
| last1 = Garey | first1 = M. R. | author1-link = Michael Garey
Line 123: Line 53:
| pages = 47–63
| pages = 47–63
| title = Proc. 6th ACM Symposium on Theory of Computing (STOC '74)
| title = Proc. 6th ACM Symposium on Theory of Computing (STOC '74)
| year = 1974}}.</ref>
| year = 1974| s2cid = 207693360 }}.</ref>
* directed planar graphs with indegree and outdegree at most two,<ref>{{citation
* directed planar graphs with indegree and outdegree at most two,<ref>{{citation
| last = Plesńik | first = J.
| last = Plesńik | first = J.
Line 160: Line 90:
* cubic subgraphs of the square grid graph.<ref>{{citation
* cubic subgraphs of the square grid graph.<ref>{{citation
| last = Buro | first = Michael
| last = Buro | first = Michael
| title = Computers and Games
| contribution = Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs
| contribution = Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs
| contribution-url = http://skatgame.net/mburo/ps/amaend.pdf
| contribution-url = http://skatgame.net/mburo/ps/amaend.pdf
| title = Conference on Computers and Games
| volume = 2063
| volume = 2063
| pages = 250–261
| pages = 250–261
| year = 2000
| doi = 10.1007/3-540-45579-5_17| series = Lecture Notes in Computer Science
| doi = 10.1007/3-540-45579-5_17| series = Lecture Notes in Computer Science
| date = 2001
| isbn = 978-3-540-43080-3
| isbn = 978-3-540-43080-3
| citeseerx = 10.1.1.40.9731
| citeseerx = 10.1.1.40.9731
Line 173: Line 103:
However, for some special classes of graphs, the problem can be solved in polynomial time:
However, for some special classes of graphs, the problem can be solved in polynomial time:


* [[k-vertex-connected graph|4-connected]] planar graphs are always Hamiltonian by a result due to Tutte, and the computational task of finding a Hamiltonian cycle in these graphs can be carried out in linear time<ref>{{citation
* [[k-vertex-connected graph|4-connected]] planar graphs are always Hamiltonian by a result due to [[W. T. Tutte|Tutte]], and the computational task of finding a Hamiltonian cycle in these graphs can be carried out in linear time<ref>{{citation
| last1 = Chiba| first1 = Norishige
| last1 = Chiba| first1 = Norishige
| last2 = Nishizeki| first2 = Takao
| last2 = Nishizeki| first2 = Takao
Line 183: Line 113:
| issue = 2
| issue = 2
| year = 1989}}</ref> by computing a so-called [[Tutte path]].
| year = 1989}}</ref> by computing a so-called [[Tutte 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<ref>{{citation
* 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,<ref>{{citation
| last1 = Schmid| first1 = Andreas
| last1 = Schmid| first1 = Andreas
| last2 = Schmidt| first2 = Jens M.
| last2 = Schmidt| first2 = Jens M.
Line 189: Line 119:
| title = Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP'18), to appear.
| title = Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP'18), to appear.
| year = 2018
| year = 2018
}}</ref>, which may be used to find Hamiltonian cycles and long cycles in generalizations of planar graphs.
}}</ref> 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; see [[Barnette's conjecture]].
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; see [[Barnette's conjecture]].


In graphs in which all vertices have odd degree, an argument related to the [[handshaking 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.<ref>{{citation
In graphs in which all vertices have odd degree, an argument related to the [[handshaking 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.<ref>{{citation
| last = Thomason | first = A. G.
| last = Thomason
| first = A. G.
| contribution = Hamiltonian cycles and uniquely edge colourable graphs
| contribution = Hamiltonian cycles and uniquely edge colourable graphs
| doi = 10.1016/S0167-5060(08)70511-9
| doi = 10.1016/S0167-5060(08)70511-9
| mr = 499124
| mr = 499124
| pages = 259–268
| pages = [https://archive.org/details/advancesingrapht0000camb/page/259 259–268]
| series = Annals of Discrete Mathematics
| series = Annals of Discrete Mathematics
| title = Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977)
| title = Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977)
| volume = 3
| volume = 3
| year = 1978
| year = 1978
| isbn = 9780720408430
| isbn = 9780720408430}}.</ref> However, finding this second cycle does not seem to be an easy computational task. [[Christos Papadimitriou|Papadimitriou]] defined the [[complexity class]] [[PPA (complexity)|PPA]] to encapsulate problems such as this one.<ref>{{citation | last = Papadimitriou| first = Christos H.| author-link = Christos Papadimitriou | doi = 10.1016/S0022-0000(05)80063-7
| url = https://archive.org/details/advancesingrapht0000camb/page/259
}}.</ref> However, finding this second cycle does not seem to be an easy computational task. [[Christos Papadimitriou|Papadimitriou]] defined the [[complexity class]] [[PPA (complexity)|PPA]] to encapsulate problems such as this one.<ref>{{citation | last = Papadimitriou| first = Christos H.| author-link = Christos Papadimitriou | doi = 10.1016/S0022-0000(05)80063-7
| issue = 3
| issue = 3
| journal = [[Journal of Computer and System Sciences]]
| journal = [[Journal of Computer and System Sciences]]
Line 209: Line 142:
| title = On the complexity of the parity argument and other inefficient proofs of existence
| title = On the complexity of the parity argument and other inefficient proofs of existence
| volume = 48
| volume = 48
| year = 1994 | mr = 1279412}}.</ref>
| year = 1994 | mr = 1279412| citeseerx = 10.1.1.321.7008
}}.</ref>

== Polynomial time verifier ==
[[File:Hamiltonian Path Problem.jpg|thumb|221x221px|The proposed solution {s,w,v,u,t} forms a valid Hamiltonian Path in the graph G.]]
The Hamiltonian path problem is [[NP-completeness|NP-Complete]] meaning a proposed solution can be verified in [[Polynomial-time|polynomial time]].<ref name=":12"/>

A verifier [[algorithm]] 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 a [[Certificate (complexity)|certificate]], c. For the Hamiltonian Path problem, c would consist of a [[String (computer science)|string]] of vertices where the first vertex is the start of the proposed path and the last is the end.<ref name=":0">{{Cite web |last=Bun |first=Mark |date=November 2022 |title=Boston University Theory of Computation |url=https://cs-people.bu.edu/mbun/courses/332_F22/slides/CS332-Lec22.pdf}}</ref> The algorithm will determine if c is a valid [[Hamiltonian path|Hamiltonian 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.<ref name=":0" /><ref>{{Cite web |last=Bretscher |first=A |date=February 5, 2021 |title=University of Toronto CSCC63 Week 7 Lecture Notes |url=http://www.utsc.utoronto.ca/~bretscher/c63/lectures/w7.pdf}}</ref>

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.<ref name=":0" />

== Applications ==

=== Networks on chip ===
[[Network on a chip|Networks on chip]] (NoC) are used in computer systems and [[Processor (computing)|processors]] serving as communication for on-chip components.<ref>{{Cite web |last=Bahn |first=Jun Ho |title=Overview of Network-on-Chip |url=https://newport.eecs.uci.edu/~nader/lab/NoCOverview.htm |website=University Of California Irvine}}</ref> The performance of NoC is determined by the method it uses to move [[Network packet|packets]] of data across a [[Computer network|network]].<ref>{{Cite book |last=Satish |first=E. G. |title=Emerging Research in Computing, Information, Communication and Applications |chapter=Comparative Performance Analysis of Routing Topology for NoC Architecture |series=Lecture Notes in Electrical Engineering |date=2022 |chapter-url=https://link.springer.com/chapter/10.1007/978-981-16-1342-5_34 |volume=790 |pages=431–440 |doi=10.1007/978-981-16-1342-5_34 |isbn=978-981-16-1341-8 |via=Springer}}</ref> The Hamiltonian Path problem can be implemented as a path-based method in [[multicast routing]]. Path-based multicast algorithms will determine if there is a Hamiltonian path from the start [[Node (networking)|node]] to each end node and send packets across the corresponding path. Utilizing this strategy guarantees [[deadlock (computer science)|deadlock]] and [[livelock]] free routing, increasing the efficiency of the NoC.<ref>{{Cite journal |last1=Bahrebar |first1=P. |last2=Stroobandt |first2=D. |date=2014 |title=Improving hamiltonian-based routing methods for on-chip networks: A turn model approach |journal=2014 Design, Automation & Test in Europe Conference & Exhibition |pages=1–4 |via=IEEE}}</ref>

=== Computer graphics ===
[[Rendering (computer graphics)|Rendering]] engines are a form of [[software]] used in [[computer graphics]] to generate images or models from input data.<ref>{{Cite web |last1=Garsiel |first1=Tali |last2=Irish |first2=Paul |date=August 5, 2011 |title=How Browsers Work |url=https://web.dev/howbrowserswork/}}</ref> In [[Three-dimensional space|three dimensional]] graphics rendering, a common input to the engine is a [[polygon 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."<ref>{{Cite journal |last1=Arkin |first1=Esther M. |last2=Mitchell |first2=Joseph S. B. |last3=Held |first3=Martin |last4=Skiena |first4=Steven S. |title=Hamiltonian Triangulations for Fast Rendering |url=https://www3.cs.stonybrook.edu/~stripe/compgeompaper.pdf |journal=Department of Computer Science Stony Brook University}}</ref> That way, only one vertex changes between each consecutive triangle. This ordering exists if the [[dual graph]] of the triangular mesh contains a Hamiltonian path.


== References ==
== References ==
{{commons category inline}}
{{commons category-inline}}
{{Reflist|30em}}
{{Reflist|30em}}
*{{citation
| first1 = Anna |last1 = Knezevic
| first2 = Greg |last2 = Cohen
| title = Some facts on Permanents in Finite Characteristics
| arxiv= 1710.01783
| year = 2017
|bibcode = 2017arXiv171001783K}}.



{{DEFAULTSORT:Hamiltonian Path Problem}}
{{DEFAULTSORT:Hamiltonian Path Problem}}

Latest revision as of 19:02, 20 August 2024

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]

Reductions

[edit]

Reduction from the path problem to the cycle problem

[edit]

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

  • In one direction, the Hamiltonian path problem for graph G can be related to the Hamiltonian cycle problem in a graph H obtained from G by adding a new universal vertex x, connecting x to all vertices of G. 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 graph G is equivalent to the Hamiltonian path problem in the graph H obtained by adding terminal (degree-one) vertices s and t attached respectively to a vertex v of G and to v', a cleaved copy of v which gives v' the same neighbourhood as v. The Hamiltonian path in H running through vertices ⁠⁠ corresponds to the Hamiltonian cycle in G running through ⁠⁠.[4]

Algorithms

[edit]

Brute force

[edit]

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

[edit]

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.

Dynamic programming

[edit]

Also, a dynamic programming algorithm of Bellman, Held, and Karp can be used to solve the problem in time O(n2 2n). 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.[6][7]

Monte Carlo

[edit]

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.657n); for bipartite graphs this algorithm can be further improved to time O(1.415n).[8]

Backtracking

[edit]

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

Boolean satisfiability

[edit]

Hamiltonian paths can be found using a SAT solver. The Hamiltonian path is NP-Complete meaning it can be mapping reduced to the 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

[edit]

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 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.

Complexity

[edit]

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

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 to Tutte, and the computational task of finding a Hamiltonian cycle in these graphs can be carried out in linear time[18] by computing a so-called Tutte 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; see Barnette's conjecture.

In graphs in which all vertices have odd degree, an argument related to the handshaking 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 the complexity class PPA to encapsulate problems such as this one.[21]

Polynomial time verifier

[edit]
The proposed solution {s,w,v,u,t} forms a valid Hamiltonian Path in the graph G.

The Hamiltonian path problem is NP-Complete meaning a proposed solution can be verified in polynomial time.[1]

A verifier algorithm 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 a certificate, c. For the Hamiltonian Path problem, c would consist of a string 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 valid Hamiltonian 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]

Applications

[edit]

Networks on chip

[edit]

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

Computer graphics

[edit]

Rendering engines are a form of software used in computer graphics to generate images or models from input data.[27] In three dimensional graphics rendering, a common input to the engine is a polygon 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 the dual graph of the triangular mesh contains a Hamiltonian path.

References

[edit]

Media related to Hamiltonian path problem at Wikimedia Commons

  1. ^ a b 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. ^ a b 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.
  4. ^ Reduction from Hamiltonian cycle to Hamiltonian path
  5. ^ Rubin, Frank (1974), "A Search Procedure for Hamilton Paths and Circuits", Journal of the ACM, 21 (4): 576–80, doi:10.1145/321850.321854, S2CID 7132716
  6. ^ Bellman, Richard (January 1962). "Dynamic Programming Treatment of the Travelling Salesman Problem". Journal of the ACM. 9 (1): 61–63. doi:10.1145/321105.321111. ISSN 0004-5411. S2CID 15649582.
  7. ^ Held, Michael; Karp, Richard M. (March 1962). "A Dynamic Programming Approach to Sequencing Problems". Journal of the Society for Industrial and Applied Mathematics. 10 (1): 196–210. doi:10.1137/0110015. ISSN 0368-4245.
  8. ^ Bjorklund, Andreas (October 2010). "Determinant Sums for Undirected Hamiltonicity". 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. IEEE. pp. 173–182. arXiv:1008.0541. doi:10.1109/focs.2010.24. ISBN 978-1-4244-8525-3.
  9. ^ Iwama, Kazuo; Nakashima, Takuya (2007), Lin, Guohui (ed.), "An Improved Exact Algorithm for Cubic Graph TSP", Computing and Combinatorics, Lecture Notes in Computer Science, vol. 4598, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 108–117, doi:10.1007/978-3-540-73545-8_13, ISBN 978-3-540-73544-1, retrieved 2023-10-07
  10. ^ Adleman, Leonard (November 1994), "Molecular computation of solutions to combinatorial problems", Science, 266 (5187): 1021–1024, Bibcode:1994Sci...266.1021A, CiteSeerX 10.1.1.54.2565, doi:10.1126/science.7973651, JSTOR 2885489, PMID 7973651.
  11. ^ Mihai Oltean (2006). A light-based device for solving the Hamiltonian path problem. Unconventional Computing. Springer LNCS 4135. pp. 217–227. arXiv:0708.1496. doi:10.1007/11839132_18.
  12. ^ "Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete". Computer Science Stack Exchange. Retrieved 2019-03-18.
  13. ^ Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), "Some simplified NP-complete problems", Proc. 6th ACM Symposium on Theory of Computing (STOC '74), pp. 47–63, doi:10.1145/800119.803884, S2CID 207693360.
  14. ^ Plesńik, J. (1979), "The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two" (PDF), Information Processing Letters, 8 (4): 199–201, doi:10.1016/0020-0190(79)90023-1.
  15. ^ Akiyama, Takanori; Nishizeki, Takao; Saito, Nobuji (1980–1981), "NP-completeness of the Hamiltonian cycle problem for bipartite graphs", Journal of Information Processing, 3 (2): 73–76, MR 0596313.
  16. ^ Itai, Alon; Papadimitriou, Christos; Szwarcfiter, Jayme (1982), "Hamilton Paths in Grid Graphs", SIAM Journal on Computing, 4 (11): 676–686, CiteSeerX 10.1.1.383.1078, doi:10.1137/0211056.
  17. ^ Buro, Michael (2001), "Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs" (PDF), Computers and Games, Lecture Notes in Computer Science, vol. 2063, pp. 250–261, CiteSeerX 10.1.1.40.9731, doi:10.1007/3-540-45579-5_17, ISBN 978-3-540-43080-3.
  18. ^ Chiba, Norishige; Nishizeki, Takao (1989), "The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs", Journal of Algorithms, 10 (2): 187–211, doi:10.1016/0196-6774(89)90012-6
  19. ^ Schmid, Andreas; Schmidt, Jens M. (2018), "Computing Tutte Paths", Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP'18), to appear.
  20. ^ Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, vol. 3, pp. 259–268, doi:10.1016/S0167-5060(08)70511-9, ISBN 9780720408430, MR 0499124.
  21. ^ Papadimitriou, Christos H. (1994), "On the complexity of the parity argument and other inefficient proofs of existence", Journal of Computer and System Sciences, 48 (3): 498–532, CiteSeerX 10.1.1.321.7008, doi:10.1016/S0022-0000(05)80063-7, MR 1279412.
  22. ^ a b c Bun, Mark (November 2022). "Boston University Theory of Computation" (PDF).
  23. ^ Bretscher, A (February 5, 2021). "University of Toronto CSCC63 Week 7 Lecture Notes" (PDF).
  24. ^ Bahn, Jun Ho. "Overview of Network-on-Chip". University Of California Irvine.
  25. ^ Satish, E. G. (2022). "Comparative Performance Analysis of Routing Topology for NoC Architecture". Emerging Research in Computing, Information, Communication and Applications. Lecture Notes in Electrical Engineering. Vol. 790. pp. 431–440. doi:10.1007/978-981-16-1342-5_34. ISBN 978-981-16-1341-8 – via Springer.
  26. ^ Bahrebar, P.; Stroobandt, D. (2014). "Improving hamiltonian-based routing methods for on-chip networks: A turn model approach". 2014 Design, Automation & Test in Europe Conference & Exhibition: 1–4 – via IEEE.
  27. ^ Garsiel, Tali; Irish, Paul (August 5, 2011). "How Browsers Work".
  28. ^ Arkin, Esther M.; Mitchell, Joseph S. B.; Held, Martin; Skiena, Steven S. "Hamiltonian Triangulations for Fast Rendering" (PDF). Department of Computer Science Stony Brook University.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Hamiltonian_path_problem&oldid=1241362622"