Hamiltonian path problem

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.

In the 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 (whether directed or undirected). Both problems are NP-complete.

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

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:

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

Algorithms

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. A search procedure by Frank Rubin 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² 2ⁿ). 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.

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ⁿ); for bipartite graphs this algorithm can be further improved to time o(1.415ⁿ).

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

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

An optical solution to the Hamiltonian problem has been proposed in . 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 $A$ defined as $\operatorname {ham} (A)=\sum _{\sigma \in H_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}$ where ${H_{n}}$ 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.

In (Knezevic & Cohen (2017)) it was shown that $\operatorname {ham} (A)=\Sigma _{J\subseteq \{2,\dots ,n\}}(-1)^{|J|}\det(A_{J})\operatorname {per} (A_{\bar {J}})$ where $A_{J}$ is the submatrix of $A$ induced by the rows and columns of $A$ indexed by $J$, and ${\bar {J}}$ is the complement of $J$ in $\{1,\dots ,n\}$, while the determinant of the empty submatrix is defined to be 1. In a field of characteristic 2 the latter equality turns into $\operatorname {ham} (A)=\Sigma _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {det} (A_{\bar {J}})$ what therefore provides an opportunity to polynomial-time calculate the Hamiltonian cycle polynomial of any unitary matrix $U$ (i.e. such that $U^{T}U=I$ where $I$ is the identity n×n-matrix), because in such a field each minor of a unitary matrix coincides with its algebraic complement: $\operatorname {ham} (U)=\operatorname {det} ^{2}(U+I_{/1})$ where $I_{/1}$ 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.

Besides, in an arbitrary ring $R$ for any skew-symmetric n×n-matrix $A$ there exists a power series in a formal variable $\varepsilon$: $U(\varepsilon )=\sum _{n=0}^{\infty }U_{n}\varepsilon ^{n}$ such that it's a unitary n×n-matrix over $R\left(\varepsilon \right)$ and $U_{0}=I$, $U_{1}=A$, while for any $U(\varepsilon )$ satisfying these conditions $\operatorname {ham} (A)$ equals the coefficient at the $n$-th power of $\varepsilon$ in the power series $\operatorname {ham} (U(\varepsilon ))$. It implies that computing, up to the $n$-th power of $\varepsilon$, 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 $\varepsilon$ is a #q-P-complete problem if $q$ isn't 2 and computing the Hamiltonian cycle polynomial of a $k$-semi-unitary matrix (i.e. an n×n-matrix $V$ such that $rank(V^{T}V-I\,)=k$) over such an extension of any ring of characteristic 2 is a #2-P-complete problem for any $k$ > 0 (because any $k$-semi-unitary matrix can be received from a unitary matrix via removing $k$ rows and $k$ columns). For $k=1$ the latter statement can be re-formulated as the #2-P-completeness of computing, for a given unitary n×n-matrix $U$ over a field of characteristic 2, the n×n-matrix $H(U)$ whose i,j-th entry is the Hamiltonian cycle polynomial of the matrix received from $U$ via removing its i-th row and j-th column. This matrix satisfies the following matrix equation: $U(H(U))^{T}=H(U)U^{T}$.

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 $\operatorname {ham} (X)=0$ for any t×t-matrix $X$ having three equal rows or, if $t$ > 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 $\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)}$ for an n×n-matrix $U$, m×m-matrices $V$ and diagonal $D$, m×n-matrix $A$ and n×m-matrix $B$.

This identity's restriction to the case when $U$ is unitary, $VD+DV^{T}+AA^{T}=I+D^{2}$ and $BD=UA^{T}$, where $I$ 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.

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 $A_{11}$ and $A_{22}$ being square, $A_{11}$ being invertible):

$\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)}$

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 alow to reduce the matrix's size by some of the above-mentioned compression operators.

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

Complexity

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:

• bipartite graphs,
• undirected planar graphs of maximum degree three,
• directed planar graphs with indegree and outdegree at most two,
• bridgeless undirected planar 3-regular bipartite graphs,
• 3-connected 3-regular bipartite graphs,
• subgraphs of the square grid graph,
• cubic subgraphs of the square grid graph.

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

References

Media related to Hamiltonian path problem at Wikimedia Commons

• Knezevic, Anna; Cohen, Greg (2017), Some facts on Permanents in Finite Characteristics, arXiv:1710.01783, Bibcode:2017arXiv171001783K.