Hubbry Logo
Hamiltonian path problemHamiltonian path problemMain
Open search
Hamiltonian path problem
Community hub
Hamiltonian path problem
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Hamiltonian path problem
Hamiltonian path problem
Hamiltonian path problem
View on Wikipedia
from Wikipedia

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]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Hamiltonian path problem

View on Grokipedia
from Grokipedia
The Hamiltonian path problem is a classic in that asks whether there exists a path in a given undirected or that visits each vertex exactly once. This path, known as a , must traverse the graph without revisiting any vertex, though edges may connect the vertices in sequence as per the graph's structure. Named after Irish mathematician , who explored related concepts in 1857 through the ""—a puzzle involving a Hamiltonian cycle on the edges of a graph—the problem gained prominence in combinatorial mathematics during the . In the context of , the decision version of the problem—determining the existence of such a path between specified start and end vertices in a —was formalized as computationally challenging in the 1970s. The Hamiltonian path problem is NP-complete, meaning it is among the hardest problems in the NP complexity class; verifying a proposed solution (a candidate path) can be done in polynomial time, but finding one generally cannot unless P=NP. Richard Karp demonstrated the NP-completeness of the related directed Hamiltonian cycle problem in his seminal 1972 paper by reducing the 3-SAT problem (known to be NP-complete) to it in polynomial time, with the path variant following via a simple reduction; showing that solving it would solve all NP problems efficiently. For undirected graphs, the problem remains NP-complete via a similar reduction from the Hamiltonian cycle problem. Beyond theory, the problem has practical implications in optimization, such as approximating solutions to the traveling salesman problem (where edge weights represent distances) and in applications like , genome sequencing, and scheduling tasks without repetition. No polynomial-time algorithm exists for the general case, but heuristics and exact solvers using dynamic programming or are employed for instances with special structures, like tournaments or planar graphs.

Definition and Background

Formal Statement

The Hamiltonian path problem is a fundamental in , asking whether a given undirected or directed contains a path that visits every vertex exactly once. Formally, given an undirected graph G=(V,E)G = (V, E) with vertex set VV of size n=∣V∣n = |V| and edge set EE, the problem determines if there exists a sequence of distinct vertices v1,v2,…,vn∈Vv_1, v_2, \dots, v_n \in V such that (vi,vi+1)∈E(v_i, v_{i+1}) \in E for all 1≤i<n1 \leq i < n. For directed graphs, edges are ordered pairs, and the condition applies accordingly. The input to the problem consists of the graph GG, typically encoded via an adjacency list (listing neighbors for each vertex) or an adjacency matrix (a boolean matrix indicating edge presence between vertices), along with the number of vertices nn. The output is a binary decision: "yes" if a Hamiltonian path exists, and "no" otherwise. This formulation treats the problem strictly as one of existence, without requiring the explicit construction or identification of the path itself. For illustration, consider the complete graph K3K_3 on three vertices connected by all possible edges, forming a triangle. This graph admits Hamiltonian paths, such as the sequence traversing vertices 1-2-3, since every pair is adjacent and all vertices are visited exactly once. The Hamiltonian path problem is distinct from the related Hamiltonian cycle problem, which seeks a closed path visiting each vertex exactly once and returning to the starting vertex.

Relation to Hamiltonian Cycle

The Hamiltonian cycle in a graph is defined as a closed path that visits each vertex exactly once before returning to the starting vertex. This differs from a , which does not require closure, but the two problems are intimately connected through simple structural modifications. A standard polynomial-time reduction from the to the Hamiltonian cycle problem involves augmenting the original undirected graph G=(V,E)G = (V, E) with a new vertex v′v' adjacent to every vertex in VV. The resulting graph G′G' has a Hamiltonian cycle if and only if GG has a Hamiltonian path: if GG contains a path visiting all vertices from some ss to tt, then G′G' admits the cycle v′→s→⋯→t→v′v' \to s \to \cdots \to t \to v'; conversely, any Hamiltonian cycle in G′G' induces a in GG by removing v′v' and its incident edges. The reverse reduction, from Hamiltonian cycle to path, can be achieved for undirected graphs by selecting an arbitrary edge {u,v}\{u, v\} in GG (assuming GG is connected and has edges), removing it to form G′G', and determining if G′G' has a Hamiltonian path from uu to vv: GG has a Hamiltonian cycle if and only if such a path exists in G′G'. Both the Hamiltonian path and cycle problems are NP-complete, as established in Karp's seminal work demonstrating their equivalence under polynomial-time reductions from known NP-complete problems like 3-SAT. The mutual reducibility implies that the problems share the same computational complexity, with the path variant directly transformable to the cycle variant (and vice versa) in linear time. This close relationship extends to algorithmic approaches: solvers designed for Hamiltonian cycles can be adapted to find paths via these O(1) graph modifications, preserving asymptotic performance while enabling bidirectional applicability in exact and heuristic methods.

History and Origins

Early Developments

The concept of traversing graphs in a specific manner traces its early roots to the 18th century, particularly through 's foundational work on what would later be known as . In 1735, Euler presented a paper to the St. Petersburg Academy addressing the Seven Bridges of Königsberg problem, which involved finding a path that crosses each bridge exactly once without repetition, though it did not require visiting every landmass (vertex) precisely once. This work, published in 1736, laid groundwork for graph traversal problems but focused on edges rather than vertices, distinguishing it from later formulations. Parallel to Euler's contributions, combinatorial puzzles involving vertex traversals emerged in the context of chess problems, notably the knight's tour, which requires a knight to visit every square on a chessboard exactly once. The earliest documented discussions of the knight's tour appear in Arabic manuscripts from around 840 AD, attributed to the scholar al-Adli ar-Rumi, who explored open and closed tours on smaller boards. By the 18th century, Euler extended this in 1759 by demonstrating a closed knight's tour on an 8x8 board, treating the problem as a vertex-covering path in the knight's graph, though solutions remained manual and puzzle-oriented rather than algorithmic. These early efforts highlighted the challenge of complete vertex traversals but predated formal graph-theoretic framing. The Hamiltonian path problem derives its name from the 19th-century work of Irish mathematician , who in 1856 began exploring systematic traversals of polyhedral graphs, particularly the dodecahedron. Hamilton's investigations extended Eulerian ideas to vertex-focused paths and cycles, culminating in the Icosian game, a puzzle he invented in 1857 that challenges players to find a cycle visiting each of the 20 vertices of a dodecahedron exactly once, with the vertices labeled with the names of cities. While the game emphasized cycles, Hamilton's underlying "Icosian calculus" implicitly addressed path constructions as precursors, published in papers in the and Proceedings of the Royal Irish Academy in 1856. Initially, Hamilton's contributions centered on recreational mathematics and polyhedral symmetries rather than computational or complexity aspects, with the Icosian game commercialized in 1859 by a London firm for £25, promoting it as an intellectual diversion. This era's focus on puzzles like the knight's tour and Icosian game underscored the problem's combinatorial allure, influencing later graph theory without immediate recognition of its decision-theoretic implications.

Key Milestones

The Hamiltonian path problem gained formal recognition in computer science during the 1950s, as graph-theoretic problems began intersecting with emerging computational paradigms and optimization techniques. This period marked the transition of combinatorial challenges from pure mathematics to algorithmic study, with early explorations in network flows and pathfinding laying groundwork for analyzing traversal problems in discrete structures. A pivotal theoretical advancement occurred in 1960 when Øystein Ore established sufficient degree conditions guaranteeing the existence of a Hamiltonian path. Ore's theorem states that a connected graph on nn vertices has a Hamiltonian path if, for every pair of non-adjacent vertices uu and vv, deg⁡(u)+deg⁡(v)≥n−1\deg(u) + \deg(v) \geq n-1. This condition extended earlier Dirac-like criteria and provided a practical tool for verifying Hamiltonicity in denser graphs, influencing subsequent sufficiency theorems in graph theory. In 1972, Richard Karp solidified the problem's status in computational complexity by including the Hamiltonian path among his 21 NP-complete problems in the seminal paper "Reducibility Among Combinatorial Problems." Karp demonstrated reductions from other hard problems, such as the vertex cover, establishing that deciding the existence of a Hamiltonian path is NP-complete for directed and undirected graphs, which spurred decades of research into exact and approximate solutions. The 1980s and 1990s saw substantial progress in heuristic and approximation methods, often leveraging connections to the traveling salesman problem (TSP). Nicos Christofides' 1976 algorithm for the metric TSP, yielding a 3/2-approximation ratio for finding near-optimal tours, was extended in this era to the s-t Hamiltonian path variant, enabling efficient heuristics for metric instances by constructing minimum spanning trees and Eulerian paths followed by shortcutting. These developments, including branch-and-bound techniques and genetic algorithms tailored for sparse graphs, improved practical solvability for large instances despite inapproximability results under standard assumptions. In the 2010s and beyond, quantum computing introduced novel approaches for approximate solving. The Harrow-Hassidim-Lloyd (HHL) algorithm (2009), which solves linear systems exponentially faster than classical methods under certain conditions, inspired hybrid quantum-classical frameworks for optimization problems like Hamiltonian path, particularly in quantum approximate optimization algorithms (QAOA). For instance, a 2022 QAOA variant specifically targets the Hamiltonian path by encoding the problem into a quantum Ising model, demonstrating potential speedups for small-scale instances on near-term quantum hardware. Recent advancements up to 2023 have focused on parameterized complexity, especially for restricted graph classes like grid graphs. A 2023 study showed that finding long directed cycles—and by extension, Hamiltonian paths—in graphs with small directed feedback vertex sets remains W-hard, even for grid-like structures, highlighting persistent challenges in fixed-parameter tractability while identifying polynomial-time solvable subclasses such as O-shaped supergrids. These results refine the boundaries of efficient algorithms for geometric and lattice-based instances.

Complexity Analysis

NP-Completeness Proof

The Hamiltonian path problem belongs to the class NP because a nondeterministic can guess a sequence of nn distinct vertices and verify it forms a path in polynomial time. Specifically, the certificate consists of an ordered list of vertices v1,v2,…,vnv_1, v_2, \dots, v_n, where the verifier checks two conditions: (1) each pair (vi,vi+1)(v_i, v_{i+1}) is an edge in the graph, requiring O(n)O(n) adjacency checks, and (2) all vertices are unique, which can be confirmed in O(n2)O(n^2) time by pairwise comparison or using a hash set in practice. The overall verification time complexity is thus T(n)=O(n2)T(n) = O(n^2). To establish NP-hardness, a polynomial-time many-one reduction from the NP-complete 3-SAT problem to the Hamiltonian path problem is constructed, as originally demonstrated by in 1972. This proof shows that solving Hamiltonian path would allow solving 3-SAT in polynomial time if a polynomial-time algorithm existed for the former, thereby proving NP-completeness. Karp's seminal work included this among 21 combinatorial problems reduced from SAT, highlighting that intractability is pervasive in optimization and sequencing tasks, forming a cornerstone of computational complexity theory by linking logical satisfiability to graph traversal. The reduction builds a directed graph GG from a 3-SAT formula ϕ\phi with nn variables and mm clauses such that GG has a Hamiltonian path from a source vertex ss to a sink vertex tt if and only if ϕ\phi is satisfiable. For each variable xix_i, a variable gadget is created: a chain of 2m+12m + 1 vertices vi,0,vi,1,…,vi,2mv_{i,0}, v_{i,1}, \dots, v_{i,2m} with bidirectional edges along the chain, allowing traversal in either direction (left-to-right for xi=x_i = true, right-to-left for false). These chains are connected end-to-end across variables, ensuring the path must traverse all variable gadgets while choosing a consistent direction for each. For each clause jj, a clause gadget vertex cjc_j is added, with incoming edges from the literals in the clause (e.g., from position 2j−12j-1 or 2j2j in the relevant variable chain depending on positive or negative polarity) and outgoing edges to the next positions, allowing the path to detour through cjc_j only if at least one literal is true under the assignment defined by the directions. The source ss connects to the start of the first chain, and the sink tt to the end of the last, forcing a full traversal. This construction ensures every clause gadget is visited exactly once via a true literal, corresponding to a satisfying assignment, and runs in O(nm)O(nm) time. The undirected version follows analogously by symmetrizing edges, preserving the NP-completeness. The Hamiltonian path problem demonstrates significant inapproximability properties. Specifically, there is no polynomial-time approximation algorithm that can approximate the length of the longest path within a factor of n1−ϵn^{1-\epsilon} for any constant ϵ>0\epsilon > 0, unless P = NP. This result is derived from the corresponding inapproximability for the Hamiltonian cycle problem, to which the path variant reduces in polynomial time. In parameterized complexity theory, the directed variant of the Hamiltonian path problem is W-hard when parameterized by directed treewidth. This hardness holds even for finding cycles of length at least a constant fraction of the number of vertices. In contrast, the undirected Hamiltonian path admits fixed-parameter tractable algorithms parameterized by (undirected) pathwidth, leveraging dynamic programming on path decompositions. The directed Hamiltonian path problem is NP-complete, distinct from the undirected case. Its NP-completeness is established via a from 3-SAT, where variable and clause gadgets are constructed to ensure that a satisfying assignment corresponds to a traversing all vertices exactly once. This reduction differs from the undirected version, which uses or vertex disjoint paths reductions. The , which seeks a simple path of maximum length in a graph, is NP-hard. This hardness persists even when restricting to optimization variants without a guaranteed , and it implies challenges in approximating the maximum path length beyond constant factors. Recent results have explored average-case hardness for the under distributions like random graphs. Assuming the (ETH), there is no polynomial-time algorithm for solving on average over certain input distributions derived from worst-case hard instances, including sparse random graphs near the connectivity threshold. This establishes that average-case instances can be as hard as worst-case ones for subexponential time solvers.

Algorithms for Solving

Exact Methods

The brute force method for determining whether a exists in a graph involves enumerating all possible of the n vertices and checking for each whether consecutive vertices in the permutation are connected by edges in the graph. This requires generating and validating n! permutations, with each validation taking O(n) time to check the n-1 edges, resulting in an overall of O(n! · n). A more efficient exact algorithm employs dynamic programming in the style of the Held-Karp approach, originally proposed for sequencing problems including those related to Hamiltonian paths. This method uses states defined by a S ⊆ V of vertices and an endpoint v ∈ S, where dp[S] represents the minimum cost (or existence for the decision version) of a path that visits exactly the vertices in S and ends at v. The is: dp[S]=min⁡u∈S∖{v}(dp[S∖{v}]+w(u,v))dp[S] = \min_{u \in S \setminus \{v\}} \left( dp[S \setminus \{v\}] + w(u, v) \right) if there is an edge from u to v with weight w(u, v); otherwise, it is infinite (or false for ). Base cases are dp[{k}] = 0 for all vertices k. A Hamiltonian path exists if there is some v such that dp[V] is finite (or true). Computing all states requires O(2^n · n^2) time, as there are 2^n subsets and for each, O(n^2) transitions are considered. Backtracking provides another exact strategy through a that incrementally builds candidate paths, adding vertices one by one while ensuring no repeats and pruning subtrees when a partial path cannot be extended to cover all vertices without violating graph edges. Historical and modern implementations of for the Hamiltonian path problem, such as those surveyed in comparative studies, demonstrate effectiveness on small to moderate graph sizes by exploiting early detection of infeasible branches. The dynamic programming method achieves exponential but subfactorial time complexity, outperforming brute force for instances up to n ≈ 20, beyond which its 2^n scaling becomes impractical on standard hardware.

Heuristic and Approximation Approaches

Heuristic and approximation approaches for the Hamiltonian path problem aim to identify viable paths in large or dense graphs where exact methods are computationally prohibitive, emphasizing computational efficiency and practical success rates over theoretical guarantees. These techniques often draw inspiration from related optimization problems like the traveling salesman problem (TSP), adapting greedy, randomized, and evolutionary strategies to construct long paths that may or may not be Hamiltonian. While they provide no worst-case performance bounds due to the of the problem, they succeed frequently on random or structured graphs, enabling applications in network design and optimization. Monte Carlo methods employ randomized sampling to explore the space of possible paths, offering probabilistic guarantees of detection in certain graph classes. A representative approach involves generating random walks or permutations and verifying if they form a , with acceptance based on path coverage; this can be tuned with acceptance probabilities derived from graph density to favor complete paths. For instance, in graphs with bounded , randomized algorithms related to the Cut&Count technique can solve the Hamiltonian cycle problem in time O(4t⋅nO(1))O(4^t \cdot n^{O(1)}) with high probability, where tt is the ; similar approaches apply to paths. These methods are particularly effective in sparse or random graphs, where the probability of sampling a valid path increases with edge density, though they may require multiple trials for low-density instances. Partial path heuristics construct solutions incrementally by extending short subpaths with greedy or rule-based choices, branches that lead to dead ends. In this framework, a partial path is tested for extendability by analyzing the connectivity of the remaining subgraph, classifying edges as forbidden (if they would disconnect components) or mandatory (if required for coverage), and only when necessary. A classic implementation starts with an initial subpath and greedily adds vertices that preserve the graph's bipartition balance or degree constraints in the on unvisited vertices. The HybridHAM algorithm, primarily designed for cycles, initiates with a greedy from the highest-degree vertex to form an initial partial path, then iteratively extends it via swaps or insertions; tests on benchmark instances show it finds solutions in about 30% of cases for graphs up to 250 vertices. This approach reduces search space exponentially through early , making it suitable for graphs up to several hundred vertices. The nearest neighbor heuristic, borrowed from TSP approximations, builds a path by starting at an arbitrary vertex and iteratively appending the unvisited vertex with the smallest "distance," interpreted as edge weight in metric graphs or simply an adjacent unvisited neighbor in unweighted ones. It operates in O(n2)O(n^2) time by maintaining a of candidates and updating distances after each addition, producing a spanning path that is often near-optimal in complete or dense graphs but can get stuck in sparse structures without . Although lacking a constant-factor approximation ratio for the general case, it serves as a baseline for path construction, with variants incorporating look-ahead to avoid premature termination. Genetic algorithms model path candidates as sequences (chromosomes) and evolve populations through selection, crossover (e.g., order crossover to preserve path validity), and (e.g., swapping adjacent vertices) to maximize a fitness function based on path length or edge coverage. These algorithms have been applied to structured graphs, such as directed layered graphs, to optimize path orderings. More recent hybrids integrate local search operators, such as improvements, to refine solutions, demonstrating high success rates on random directed graphs with 100 vertices. In the 2020s, techniques, particularly graph neural networks (GNNs), have been explored for related problems like predicting Hamiltonian cycles by learning patterns from labeled graph datasets. For example, a compact message-passing GNN with about 22,000 parameters, trained on Erdős-Rényi random graphs of size 25, can predict cycles with success rates of 75% for n=25, 55% for n=150, and 48% for n=200, outperforming some traditional heuristics. Similar data-driven approaches hold potential for Hamiltonian paths.

Reductions to Other Problems

One common polynomial-time reduction transforms an instance of the Hamiltonian path problem into an instance of the Hamiltonian cycle problem. Given an undirected graph G=(V,E)G = (V, E) with ∣V∣=n|V| = n, construct a new graph G′G' by adding a universal vertex uu adjacent to every vertex in VV. This adds nn new edges and can be done in O(n)O(n) time. The graph GG has a Hamiltonian path if and only if G′G' has a Hamiltonian cycle, as any cycle in G′G' must pass through uu and connect two vertices in GG via paths that cover all vertices exactly once, yielding a Hamiltonian path upon removal of uu. The Hamiltonian path problem also reduces in polynomial time to the 3-SAT problem via a direct encoding that models the path as a of vertices. For a graph GG with vertices labeled 11 to nn, introduce Boolean variables xi,jx_{i,j} for 1≤i,j≤n1 \leq i,j \leq n, where xi,jx_{i,j} is true if vertex jj occupies position ii in the path. The CNF formula includes clauses ensuring: (1) each position ii has exactly one vertex (⋁j=1nxi,j\bigvee_{j=1}^n x_{i,j} and ¬xi,j∨¬xi,k\neg x_{i,j} \lor \neg x_{i,k} for j≠kj \neq k); (2) each vertex jj appears exactly once (⋁i=1nxi,j\bigvee_{i=1}^n x_{i,j} and ¬xi,j∨¬xk,j\neg x_{i,j} \lor \neg x_{k,j} for i≠ki \neq k); and (3) consecutive positions ii and i+1i+1 are adjacent in GG (¬xi,j∨¬xi+1,k\neg x_{i,j} \lor \neg x_{i+1,k} for all non-edges (j,k)∉E(j,k) \notin E). This formula has O(n2)O(n^2) variables and O(n3)O(n^3) clauses, is 3-CNF after standard conversion if needed, and is satisfiable if and only if GG has a Hamiltonian path. This SAT reduction facilitates solving instances using modern SAT solvers. For example, encodings tested with solvers like Kissat solve instances up to n≈100n \approx 100 vertices in dense graphs within reasonable time, though performance varies by graph structure and encoding optimizations such as vertex elimination. A exists from the problem to the problem (and similarly to Hamiltonian cycle), enabling the use of Hamiltonian path solvers for instances. Given a graph H=(VH,EH)H = (V_H, E_H) and integer kk, construct a new graph GG with kk "cover" vertices u1,…,uku_1, \dots, u_k corresponding to potential cover elements, plus s for each edge in EHE_H. Each edge consists of paths that can only be traversed if at least one endpoint is "selected" via routing through the corresponding uiu_i; uncovered edges block all Hamiltonian paths by forcing dead ends in the . The full construction connects these in a linear , ensuring a Hamiltonian path in GG exists if and only if HH has a of size at most kk. This -based approach runs in time relative to ∣VH∣+∣EH∣|V_H| + |E_H|. Unconventional reductions include formulations as integer linear programs (ILPs), where binary variables xi,jx_{i,j} indicate if vertex jj follows vertex ii in the path, subject to constraints for in/out-degrees (exactly 1 for intermediate vertices, adjusted for endpoints) and subtour elimination via MTZ inequalities like ui−uj+nxi,j≤n−1u_i - u_j + n x_{i,j} \leq n-1 for positions uiu_i. Feasibility of this ILP (with O(n2)O(n^2) variables and constraints) corresponds to a , solvable via ILP solvers like CPLEX for moderate nn. Reductions to quantum frameworks, such as encoding into quantum approximate optimization algorithm (QAOA) instances for variational quantum solvers, map the path constraints to (QUBO) forms, though practical utility remains limited by current quantum hardware scale.

Verification and Decision

Polynomial-Time Verifier

The polynomial-time verifier for the Hamiltonian path problem operates on an input graph G=(V,E)G = (V, E) with n=∣V∣n = |V| vertices and m=∣E∣m = |E| edges, along with a certificate consisting of an ordered of nn vertices v1,v2,…,vnv_1, v_2, \dots, v_n. The algorithm first confirms that the sequence contains each vertex exactly once by marking vertices in a set or , which requires O(n)O(n) time. It then checks, for each i=1i = 1 to n−1n-1, whether the edge (vi,vi+1)(v_i, v_{i+1}) exists in GG; using an representation, this verification takes O(n+m)O(n + m) time overall, as each edge check scans the relevant adjacency list entries. The total running time of this verifier is O(n+m)O(n + m), which is polynomial in the input size, as both nn and mm are at most O(n2)O(n^2). This efficient verification procedure demonstrates that the Hamiltonian path problem belongs to the NP, where "yes" instances have short certificates that can be checked quickly, in contrast to the apparent hardness of constructing such a path from scratch. For weighted graphs, where the decision problem asks if there exists a of total weight at most kk, the verifier extends the above by computing the sum of the weights of the edges (vi,vi+1)(v_i, v_{i+1}) and checking if it is ≤k\leq k, adding only O(n)O(n) time to the process.

Counting Variants

The counting variant of the problem seeks to determine the exact number of distinct in a given graph, distinguishing it from the decision version by requiring enumeration rather than mere existence. This problem belongs to the #P, which captures the computational difficulty of counting the accepting paths of a nondeterministic polynomial-time . Specifically, counting is #P-complete, even for directed and undirected graphs, as proven by Valiant through parsimonious reductions that preserve the number of solutions from other #P-complete problems like #SAT. This completeness implies that no polynomial-time algorithm exists unless #P = P, and it underscores the inherent hardness beyond the NP-complete decision problem. A notable reduction establishing this #P-hardness originates from the problem of of a 0-1 matrix, which Valiant also showed to be . The construction yields a directed with n row vertices r1,…,rnr_1, \dots, r_n and n column vertices c1,…,cnc_1, \dots, c_n. Edges exist from rir_i to cjc_j if the matrix entry aij=1a_{i j} = 1, and from every cjc_j to ri+1r_{i+1} for i<ni < n. The number of Hamiltonian paths starting at r1r_1 precisely equals the permanent of the matrix, given by \perm(A)=∑σ∈Sn∏i=1nai,σ(i),\perm(A) = \sum_{\sigma \in S_n} \prod_{i=1}^n a_{i, \sigma(i)}, where SnS_n is the set of permutations of {1,…,n}\{1, \dots, n\}. This demonstrates that counting Hamiltonian paths is #P-hard even when restricted to s, as the reduction is polynomial-time and preserves counts exactly. Exact algorithms for counting Hamiltonian paths rely on dynamic programming, extending the framework originally developed by Held and Karp for the traveling salesman problem. Define dp[S]dp[S] as the number of paths that visit exactly the vertices in subset S⊆VS \subseteq V and end at vertex v∈Sv \in S. The recurrence is dp[S]=∑u∈S∖{v}(u,v)∈Edp[S∖{v}]dp[S] = \sum_{\substack{u \in S \setminus \{v\} \\ (u, v) \in E}} dp[S \setminus \{v\}], with base case dp[{v}]=1dp[\{v\}] = 1 for each vv. Computing this for all subsets and vertices yields the total count by summing over all possible ending vertices for S=VS = V, achieving O(2nn2)O(2^n n^2) and space O(2nn)O(2^n n). This approach, while exponential, provides the fastest known exact method for moderate nn. Applications of counting Hamiltonian paths appear in probabilistic graph theory, particularly for analyzing s. For instance, the expected number of Hamiltonian paths in a G(n,p)G(n, p) with edge probability pp can be computed using linearity of expectation over all possible vertex orderings, where each potential path contributes pn−1p^{n-1}. If this expectation exceeds 1, the guarantees the existence of at least one such path with positive probability, aiding thresholds for Hamiltonicity in models like Erdős–Rényi graphs. Such counts thus inform asymptotic properties and phase transitions in graph ensembles.

Applications and Extensions

Hardware and Network Design

In networks on chip (NoC), Hamiltonian paths play a crucial role in data between cores in multi-core processors, enabling adaptive communication schemes that minimize latency and avoid deadlocks. These paths are particularly effective in topologies, where they provide a systematic ordering of nodes to facilitate , allowing packets to traverse alternative routes without congestion. For instance, Hamiltonian-based odd-even turn models have been developed to maximize adaptivity in 2D NoCs, outperforming deterministic methods by distributing traffic more evenly across the interconnect. This approach ensures efficient resource utilization in systems, where latency reduction is critical for overall chip performance. In very-large-scale integration (VLSI) design, the Hamiltonian path problem addresses wire routing challenges by determining non-overlapping paths for interconnects, such as power and ground lines, to prevent short circuits and signal interference. A seminal method uses a Hamiltonian cycle to partition the chip surface into distinct regions—one for power (VDD) and one for ground (GND)—allowing trees of wires to be routed within each region without crossings. This technique, applied during the power-routing phase, simplifies layout verification and reduces design complexity in single-layer metal routing. By guaranteeing a cycle that visits all modules exactly once, it ensures complete coverage while maintaining electrical integrity. Research from the 2000s, published in IEEE proceedings, highlighted NoC topologies like graphs that inherently guarantee Hamiltonian paths, supporting scalable and fault-tolerant routing in emerging multi-core architectures. structures, with their wrap-around connections, facilitate cycle-based embeddings that enable efficient and operations without virtual channels. For example, algorithms for torus-embedded hypercubes were proposed to enhance interconnect performance in parallel systems. These findings laid the groundwork for deadlock-free protocols in wormhole-routed networks. Advancements as of 2025 include hybrid quantum graph algorithms for approximating Hamiltonian paths using quantum array search techniques, with applications to path discovery in noisy intermediate-scale quantum (NISQ) environments. Separately, is being integrated into quantum chip design to optimize layouts and connectivity, combining with and semiconductors.

Computational Geometry and Graphics

In , variants of the traveling salesman problem (TSP), which seek approximate Hamiltonian paths or cycles, are employed to generate efficient tours for rendering and modeling tasks. For instance, in 3D object reconstruction, view planning algorithms use the shortest Hamiltonian path to sequence camera positions that maximize coverage while minimizing motion, enabling complete and fast scanning of unknown objects with minimal redundancy. This approach is particularly useful in autonomous systems where computational resources limit exhaustive searches, providing a near-optimal traversal of derived from surface normals or feature points. Additionally, Hamiltonian paths facilitate triangle stripification in mesh rendering, where the of a triangulated surface is traversed to produce continuous strips of s, reducing vertex processing overhead and improving GPU efficiency in real-time graphics pipelines. Seminal work established that Hamiltonian triangulations exist for certain planar graphs, allowing strips that visit each triangle exactly once without redundant vertex submissions. In (PCB) layout, Hamiltonian paths optimize feeder rack assignments during automated assembly, modeling component placements as graph vertices to find short paths that sequence pick-and-place operations across multiple machines. By computing Hamiltonian paths for pairs of feeder locations using TSP heuristics like farthest insertion, the method prioritizes component types based on path lengths, minimizing table movements and assembly time for diverse board types. This geometric routing ensures collision-free traversals in the layout plane, aligning with principles for planar graphs. The in relates to Hamiltonian paths through visibility graphs, where vertices represent polygon corners and edges indicate mutual . Visibility graphs of simple always contain a Hamiltonian cycle formed by the boundary edges. Under certain conditions, such as when endpoints form disjoint segments, a can connect all points via visible edges, aiding in guarding or patrolling tasks. Open questions include the complexity of finding Hamiltonian paths between specific vertices or recognizing visibility graphs in general. Hamiltonian paths appear in robot motion planning for collision-free traversals, particularly in constrained environments like polygonal obstacles. For snake-like , which must maneuver without self-intersection, the problem reduces to finding a in a configuration graph of joint positions, proven on grids but fixed-parameter tractable for small robot sizes using color-coding techniques. This ensures a sequence of configurations that visits all required states while avoiding obstacles, scalable for real-world deployments in tight spaces. Recent applications in (VR) and (AR) leverage Hamiltonian path-inspired sequencing for path-based animations, such as generating smooth, non-repeating trajectories for immersive tours or object manipulations in 3D scenes. In VR environments, these paths optimize animation flows to visit key viewpoints or interactive elements exactly once, enhancing user engagement in educational or exploratory simulations without redundant motion.

Biological and Optimization Contexts

The Hamiltonian path problem finds significant application in bioinformatics, particularly in genome assembly, where reconstructing sequence from short, overlapping reads is formulated as identifying a in an overlap graph. In this model, each read represents a vertex, and edges connect vertices based on the overlap between reads; a through all vertices corresponds to the original by aligning the overlaps without repetition. This approach, central to the overlap-layout-consensus (OLC) paradigm, was highlighted in foundational work on computational , though practical implementations often approximate the NP-hard path due to graph complexity. In protein folding, Hamiltonian path models provide a framework for predicting secondary structures by representing the polypeptide chain as a path on a lattice graph, where vertices denote amino acid positions and edges reflect possible backbone conformations that minimize energy. This abstraction captures the sequential connectivity of the protein chain while optimizing for non-local interactions, such as hydrogen bonds in alpha-helices or beta-sheets, to form stable secondary elements. Reverse Hamiltonian path approaches have been explored to reverse-engineer folding trajectories from known structures, aiding in the design of proteins with desired folds. Hamiltonian paths also appear in DNA self-assembly models, such as tile assembly, where paths represent the sequential binding of DNA tiles to form complex nanostructures, enabling algorithmic self-assembly for computations. Beyond biology, the Hamiltonian path problem underpins optimization in scheduling, where job sequencing on machines is modeled as finding a minimum-cost path visiting each job exactly once to minimize completion time or setup costs. For instance, in flexible manufacturing systems, the sequence of operations forms a path in a graph of jobs and resources, with edge weights representing transition times; solving this aids in just-in-time . Heuristic methods, such as branch-and-bound variants, are commonly applied for large-scale instances due to the problem's intractability. In , approximations to the appear in problems (VRP), particularly open variants where routes start from a depot and end at a without returning, effectively seeking a path covering all demand points with capacity constraints. Clustered formulations use to order visits within groups, reducing total travel distance; approximation algorithms achieve ratios near 3/2 for such cases, enabling scalable solutions for . These models extend to heterogeneous fleets, where types influence path feasibility.

References

  1. https://mathworld.wolfram.com/HamiltonianPath.html
  2. https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/1dee182d301235b901119a0ff57f05e2_MIT6_046JS15_Recitation8.pdf
  3. https://mathworld.wolfram.com/IcosianGame.html
  4. http://www.cs.toronto.edu/~ashe/ham-path-notes.pdf
  5. https://www.cs.purdue.edu/homes/hosking/197/canon/karp.pdf
  6. https://people.csail.mit.edu/virgi/6.s078/lecture17.pdf
  7. https://link.springer.com/chapter/10.1007/978-3-030-81588-2_9
  8. https://arxiv.org/pdf/2309.09228
  9. https://www.cs.cornell.edu/courses/cs722/2000sp/karp.pdf
  10. https://mathworld.wolfram.com/HamiltonianCycle.html
  11. https://student.cs.uwaterloo.ca/~cs466/Old_courses/F14/5-NPCompleteness.pdf
  12. https://www.researchgate.net/publication/221580898_Reducibility_Among_Combinatorial_Problems
  13. https://courses.cs.washington.edu/courses/cse417/21wi/lecture/23-reductions3.pdf
  14. https://old.maa.org/press/periodicals/convergence/leonard-eulers-solution-to-the-konigsberg-bridge-problem
  15. https://www.mayhematics.com/t/1n.htm
  16. http://eulerarchive.maa.org/hedi/HEDI-2006-04.pdf
  17. https://www.emis.de/classics/Hamilton/PRIAIcos.pdf
  18. https://www.maths.tcd.ie/pub/HistMath/People/Hamilton/Icosian/
  19. https://homepages.cwi.nl/~lex/files/histco.pdf
  20. https://www.whitman.edu/mathematics/cgt_online/book/section05.03.html
  21. https://www.sciencedirect.com/science/article/pii/S0315086020300240
  22. https://theory.epfl.ch/anhc/pathslil.pdf
  23. https://link.aps.org/doi/10.1103/PhysRevLett.103.150502
  24. A Hamiltonian path, also called a Hamilton path, is a graph path between two vertices of a graph that visits each vertex exactly once.
  25. https://drops.dagstuhl.de/storage/00lipics/lipics-vol274-esa2023/LIPIcs.ESA.2023.65/LIPIcs.ESA.2023.65.pdf
  26. https://www.mdpi.com/2227-7390/11/12/2712
  27. https://www.cs.toronto.edu/~ashe/ham-path-notes.pdf
  28. https://arxiv.org/abs/2308.06145
  29. https://ieeexplore.ieee.org/document/6108160
  30. https://www.sciencedirect.com/science/article/pii/S030439752100092X
  31. https://epubs.siam.org/doi/10.1137/0110015
  32. https://arxiv.org/abs/2107.00314
  33. https://developers.google.com/optimization/reference/graph/hamiltonian_path
  34. https://arxiv.org/abs/1803.00927
  35. https://onlinelibrary.wiley.com/doi/10.1155/2018/9328103
  36. https://arxiv.org/abs/2306.06523
  37. https://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20111018.pdf
  38. https://drops.dagstuhl.de/storage/00lipics/lipics-vol307-cp2024/LIPIcs.CP.2024.40/LIPIcs.CP.2024.40.pdf
  39. https://cstheory.stackexchange.com/questions/16647/hamiltonian-cycle-as-an-integer-linear-programming-problem
  40. https://arxiv.org/pdf/2204.13539
  41. https://www.khoury.northeastern.edu/home/vkp/390-fl07/NP-Examples.pdf
  42. https://www.cs.swarthmore.edu/~fontes/cs46/20s/misc/Sipser-ch7.pdf
  43. https://people.cs.umass.edu/~marius/class/cs501/lec22-nup.pdf
  44. https://people.eecs.berkeley.edu/~sinclair/cs294/n2.pdf
  45. https://dl.acm.org/doi/10.5555/2616606.2616902
  46. https://past.date-conference.com/proceedings-archive/2017/pyear/PAPERS/2014/DATE14/PDFFILES/09.2_5_IP4-13.PDF
  47. https://dl.acm.org/doi/pdf/10.5555/800032.800757
  48. https://dspace.mit.edu/bitstream/handle/1721.1/15575/11758522-MIT.pdf?sequence=2
  49. https://jonuns.com/index.php/journal/article/view/1507
  50. https://www.researchgate.net/publication/4371184_Hamiltonian-cycle-based_multicasting_on_wormhole-routed_torus_networks
  51. https://qce.quantum.ieee.org/2025/wp-content/uploads/sites/12/2025/09/QCE25-Technical-Paper-Sessions.pdf
  52. https://www.researchgate.net/publication/392701710_AI-Driven_Quantum_Chip_Design_Integrating_Semiconductors_Nanotechnology_and_Machine_Learning
  53. https://arxiv.org/pdf/2304.00910
  54. https://www.palfrader.org/research/misc/2011-tristrips.pdf
  55. https://orbi.uliege.be/bitstream/2268/202757/1/EJOR_PCB_MultipleMachines.pdf
  56. https://www.science.smith.edu/~jorourke/books/ArtGalleryTheorems/Art_Gallery_Full_Book.pdf
  57. https://people.inf.ethz.ch/hoffmann/pub/pre/ht-sevgh-03.pdf
  58. https://www.jair.org/index.php/jair/article/view/11864
  59. https://academic.oup.com/bioinformatics/article/32/17/i494/2450780
  60. https://cs.brown.edu/courses/csci1820/spring-2026/resources/ch2/Pevzner_2001.pdf
  61. https://www.researchgate.net/publication/288548976_Study_on_Protein_Structure_Based_on_Reverse_Hamilton_Path_Models
  62. https://www.propulsiontechjournal.com/index.php/journal/article/download/1937/1316/3531
  63. https://www.dna.caltech.edu/papers/Tiles.pdf
  64. https://opus4.kobv.de/opus4-zib/files/532/TR-96-03.pdf
  65. https://epubs.siam.org/doi/10.1137/0803002
  66. https://www.researchgate.net/publication/229045757_Hamiltonian_paths_in_large_clustered_routing_problems
  67. https://journals.sagepub.com/doi/10.5772/60086
Add your contribution
Related Hubs
User Avatar
No comments yet.