Hamiltonian path problem

The Hamiltonian path problem is a central topic in graph theory and complexity theory. In graph theory, a graph is a collection of dots called vertices connected by lines called edges. A Hamiltonian path is a specific route through a graph that visits every single vertex exactly once. If the path ends at the same vertex where it began, it is called a Hamiltonian cycle.

This problem can be directed, meaning the lines have a specific direction, or undirected. Sometimes, a problem will specify a required starting vertex, $s$, and an ending vertex, $t$. Determining if such a path exists is a fundamental challenge in computer science.

To understand how these problems relate, mathematicians use a process called reduction. You can turn a Hamiltonian path problem into a Hamiltonian cycle problem by adding a new universal vertex, $x$, to the graph. This new vertex connects to every other vertex in the original graph. This shows that finding a path is not significantly slower than finding a cycle in the worst case. Conversely, a Hamiltonian cycle problem can be converted into a path problem. This is done by adding two terminal vertices, $s$ and $t$, to specific parts of the graph. These methods allow researchers to use the same logic to solve different versions of the puzzle.

Finding these paths is notoriously difficult for computers. The problem belongs to a class known as NP-complete problems. This status was documented by Richard Karp in his list of 21 NP-complete problems and in the work of Michael Garey and David S. Johnson. Being NP-complete means that finding a solution is hard, but verifying a suggested solution is easy. A verifier can take a proposed path, called a certificate, and check it in polynomial time. The verifier simply confirms that every vertex appears exactly once, that the path starts and ends at the correct spots, and that every step follows an existing edge in the graph.

Several algorithms exist to tackle this complexity. A brute force approach tries every possible sequence of vertices, but this is extremely slow. For a graph with $n$ vertices, there are $n!$ (n factorial) possible sequences. To improve speed, Frank Rubin developed a search procedure that classifies edges into three types: those that must be in the path, those that cannot be, and undecided edges. Another method, dynamic programming, was developed by Bellman, Held, and Karp. This method uses the time complexity $O(n^2 2^n)$ and works by building solutions for larger sets of vertices using information from smaller ones.

More advanced mathematical techniques offer even faster results for certain graphs. Andreas Björklund used the inclusion-exclusion principle to create a Monte Carlo algorithm. This method can solve the Hamiltonian cycle problem in $O(1.657^n)$ time for arbitrary graphs, and even faster at $O(1.415^n)$ for bipartite graphs. For graphs where each vertex has a maximum degree of three, backtracking searches can find a cycle in $O(1.251^n)$ time. Because the problem is NP-complete, it can also be mapped to the 3-SAT problem, which is a famous problem in logic and computer science.

Because standard computers struggle with these tasks, scientists have explored unconventional computing models. Leonard Adleman demonstrated that a DNA computer could solve the Hamiltonian path problem. This method uses the massive parallelism of chemical reactions to find a path in a number of steps linear to the number of vertices. However, it requires a factorial number of DNA molecules to function. Another proposal involves an optical solution using light, cables, and beam splitters. While interesting, this approach requires an amount of energy that grows exponentially with the number of nodes.

These mathematical concepts have very practical uses in modern technology. In computer engineering, they are used in Networks on Chip (NoC). These networks allow different parts of a processor to communicate. Using Hamiltonian paths in multicast routing can ensure that data packets move efficiently without causing deadlocks.

Additionally, the problem is vital in 3D computer graphics. When rendering a polygon mesh made of triangles, ordering the triangles so they share faces can speed up rendering by up to a factor of three. This is possible if the dual graph of the mesh contains a Hamiltonian path.