Fact-checked by Grok 2 weeks ago

Hamiltonian path problem

The Hamiltonian path problem is a classic decision problem in graph theory that asks whether there exists a path in a given undirected or directed graph that visits each vertex exactly once.^[1] This path, known as a Hamiltonian path, must traverse the graph without revisiting any vertex, though edges may connect the vertices in sequence as per the graph's structure.^[2] Named after Irish mathematician William Rowan Hamilton, who explored related concepts in 1857 through the "icosian game"—a puzzle involving a Hamiltonian cycle on the edges of a dodecahedron graph—the problem gained prominence in combinatorial mathematics during the 19th century.^[3] In the context of computer science, the decision version of the problem—determining the existence of such a path between specified start and end vertices in a directed graph—was formalized as computationally challenging in the 1970s.^[4] 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.^[2] 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.^[5] For undirected graphs, the problem remains NP-complete via a similar reduction from the Hamiltonian cycle problem.^[4] 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 circuit design, genome sequencing, and scheduling tasks without repetition.^[6] No polynomial-time algorithm exists for the general case, but heuristics and exact solvers using dynamic programming or integer linear programming are employed for instances with special structures, like tournaments or planar graphs.^[2]

Definition and Background

Formal Statement

The Hamiltonian path problem is a fundamental decision problem in graph theory, asking whether a given undirected or directed graph contains a path that visits every vertex exactly once. Formally, given an undirected graph G = (V, E) with vertex set V of size n = |V| and edge set E, the problem determines if there exists a sequence of distinct vertices v_1, v_2, \dots, v_n \in V such that (v_i, v_{i+1}) \in E for all $1 \leq i < n. For directed graphs, edges are ordered pairs, and the condition applies accordingly.^[7]^[8] The input to the problem consists of the graph G, 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 n. 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.^[9] For illustration, consider the complete graph K_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.^[7] 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.^[9]

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.^[10] This differs from a Hamiltonian path, which does not require closure, but the two problems are intimately connected through simple structural modifications. A standard polynomial-time reduction from the Hamiltonian path problem to the Hamiltonian cycle problem involves augmenting the original undirected graph G = (V, E) with a new vertex v' adjacent to every vertex in V. The resulting graph G' has a Hamiltonian cycle if and only if G has a Hamiltonian path: if G contains a path visiting all vertices from some s to t, then G' admits the cycle v' \to s \to \cdots \to t \to v'; conversely, any Hamiltonian cycle in G' induces a Hamiltonian path in G by removing v' and its incident edges.^[11] The reverse reduction, from Hamiltonian cycle to path, can be achieved for undirected graphs by selecting an arbitrary edge \{u, v\} in G (assuming G is connected and has edges), removing it to form G', and determining if G' has a Hamiltonian path from u to v: G has a Hamiltonian cycle if and only if such a path exists in G'.^[9] 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.^[12] 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.^[13]

History and Origins

Early Developments

The concept of traversing graphs in a specific manner traces its early roots to the 18th century, particularly through Leonhard Euler's foundational work on what would later be known as Eulerian paths. 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 Hamiltonian formulations.^[14] 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.^[15]^[16] The Hamiltonian path problem derives its name from the 19th-century work of Irish mathematician William Rowan Hamilton, 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 Philosophical Magazine and Proceedings of the Royal Irish Academy in 1856.^[17]^[18] 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.^[18]

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.^[19] 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 n vertices has a Hamiltonian path if, for every pair of non-adjacent vertices u and v, \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.^[20] 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.^[9] 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.^[21]^[22] 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.^[23] 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^[24]-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.^[25]^[26]

Complexity Analysis

NP-Completeness Proof

The Hamiltonian path problem belongs to the class NP because a nondeterministic Turing machine can guess a sequence of n distinct vertices and verify it forms a path in polynomial time. Specifically, the certificate consists of an ordered list of vertices v_1, v_2, \dots, v_n, where the verifier checks two conditions: (1) each pair (v_i, v_{i+1}) is an edge in the graph, requiring O(n) adjacency checks, and (2) all vertices are unique, which can be confirmed in O(n^2) time by pairwise comparison or using a hash set in practice. The overall verification time complexity is thus T(n) = O(n^2).^[27] 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 Karp 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.^[5] The reduction builds a directed graph G from a 3-SAT formula \phi with n variables and m clauses such that G has a Hamiltonian path from a source vertex s to a sink vertex t if and only if \phi is satisfiable. For each variable x_i, a variable gadget is created: a chain of $2m + 1 vertices v_{i,0}, v_{i,1}, \dots, v_{i,2m} with bidirectional edges along the chain, allowing traversal in either direction (left-to-right for 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 j, a clause gadget vertex c_j is added, with incoming edges from the literals in the clause (e.g., from position $2j-1 or $2j in the relevant variable chain depending on positive or negative polarity) and outgoing edges to the next positions, allowing the path to detour through c_j only if at least one literal is true under the assignment defined by the directions. The source s connects to the start of the first chain, and the sink t 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) time. The undirected version follows analogously by symmetrizing edges, preserving the NP-completeness.^[27]^[5] 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 n^{1-\epsilon} for any constant \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^[24]-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.^[28]^[29] The directed Hamiltonian path problem is NP-complete, distinct from the undirected case. Its NP-completeness is established via a polynomial-time reduction from 3-SAT, where variable and clause gadgets are constructed to ensure that a satisfying assignment corresponds to a Hamiltonian path traversing all vertices exactly once. This reduction differs from the undirected version, which uses vertex cover or vertex disjoint paths reductions. The longest path problem, 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 Hamiltonian path, and it implies challenges in approximating the maximum path length beyond constant factors.^[30] Recent results have explored average-case hardness for the Hamiltonian path problem under distributions like random graphs. Assuming the exponential time hypothesis (ETH), there is no polynomial-time algorithm for solving Hamiltonian path 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 Hamiltonian path exists in a graph involves enumerating all possible permutations 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 time complexity of O(n! · n).^[6] 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.^[31] This method uses states defined by a subset 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 recurrence relation is:

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 existence). 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.^[31] Backtracking provides another exact strategy through a depth-first search 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 backtracking 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.^[32] 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.^[33]

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 NP-completeness 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 Hamiltonian path, 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 treewidth, randomized algorithms related to the Cut&Count technique can solve the Hamiltonian cycle problem in time O(4^t \cdot n^{O(1)}) with high probability, where t is the treewidth; similar approaches apply to paths.^[34] 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, pruning 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 backtracking 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 induced subgraph on unvisited vertices. The HybridHAM algorithm, primarily designed for cycles, initiates with a greedy depth-first search 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.^[35] This approach reduces search space exponentially through early pruning, 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(n^2) time by maintaining a priority queue 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 backtracking. 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 mutation (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 2-opt improvements, to refine solutions, demonstrating high success rates on random directed graphs with 100 vertices. In the 2020s, machine learning 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.^[36]

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) with |V| = n, construct a new graph G' by adding a universal vertex u adjacent to every vertex in V. This adds n new edges and can be done in O(n) time. The graph G has a Hamiltonian path if and only if G' has a Hamiltonian cycle, as any cycle in G' must pass through u and connect two vertices in G via paths that cover all vertices exactly once, yielding a Hamiltonian path upon removal of u. The Hamiltonian path problem also reduces in polynomial time to the 3-SAT problem via a direct encoding that models the path as a permutation of vertices. For a graph G with vertices labeled $1 to n, introduce Boolean variables x_{i,j} for $1 \leq i,j \leq n, where x_{i,j} is true if vertex j occupies position i in the path. The CNF formula includes clauses ensuring: (1) each position i has exactly one vertex (\bigvee_{j=1}^n x_{i,j} and \neg x_{i,j} \lor \neg x_{i,k} for j \neq k); (2) each vertex j appears exactly once (\bigvee_{i=1}^n x_{i,j} and \neg x_{i,j} \lor \neg x_{k,j} for i \neq k); and (3) consecutive positions i and i+1 are adjacent in G (\neg x_{i,j} \lor \neg x_{i+1,k} for all non-edges (j,k) \notin E). This formula has O(n^2) variables and O(n^3) clauses, is 3-CNF after standard conversion if needed, and is satisfiable if and only if G has a Hamiltonian path.^[37] This SAT reduction facilitates solving Hamiltonian path instances using modern SAT solvers. For example, encodings tested with solvers like Kissat solve instances up to n \approx 100 vertices in dense graphs within reasonable time, though performance varies by graph structure and encoding optimizations such as vertex elimination.^[38] A polynomial-time reduction exists from the vertex cover problem to the Hamiltonian path problem (and similarly to Hamiltonian cycle), enabling the use of Hamiltonian path solvers for vertex cover instances. Given a graph H = (V_H, E_H) and integer k, construct a new graph G with k "cover" vertices u_1, \dots, u_k corresponding to potential cover elements, plus gadgets for each edge in E_H. Each edge gadget consists of paths that can only be traversed if at least one endpoint is "selected" via routing through the corresponding u_i; uncovered edges block all Hamiltonian paths by forcing dead ends in the gadget. The full construction connects these in a linear arrangement, ensuring a Hamiltonian path in G exists if and only if H has a vertex cover of size at most k. This gadget-based approach runs in polynomial time relative to |V_H| + |E_H|. Unconventional reductions include formulations as integer linear programs (ILPs), where binary variables x_{i,j} indicate if vertex j follows vertex i 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 u_i - u_j + n x_{i,j} \leq n-1 for positions u_i. Feasibility of this ILP (with O(n^2) variables and constraints) corresponds to a Hamiltonian path, solvable via ILP solvers like CPLEX for moderate n.^[39] Reductions to quantum frameworks, such as encoding into quantum approximate optimization algorithm (QAOA) instances for variational quantum solvers, map the path constraints to quadratic unconstrained binary optimization (QUBO) forms, though practical utility remains limited by current quantum hardware scale.^[40]

Verification and Decision

Polynomial-Time Verifier

The polynomial-time verifier for the Hamiltonian path problem operates on an input graph G = (V, E) with n = |V| vertices and m = |E| edges, along with a certificate consisting of an ordered sequence of n vertices v_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 array, which requires O(n) time. It then checks, for each i = 1 to n-1, whether the edge (v_i, v_{i+1}) exists in G; using an adjacency list representation, this verification takes O(n + m) time overall, as each edge check scans the relevant adjacency list entries.^[2]^[41] The total running time of this verifier is O(n + m), which is polynomial in the input size, as both n and m are at most O(n^2). This efficient verification procedure demonstrates that the Hamiltonian path problem belongs to the complexity class 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.^[42]^[43] For weighted graphs, where the decision problem asks if there exists a Hamiltonian path of total weight at most k, the verifier extends the above by computing the sum of the weights of the edges (v_i, v_{i+1}) and checking if it is \leq k, adding only O(n) time to the process.^[9]

Counting Variants

The counting variant of the Hamiltonian path problem seeks to determine the exact number of distinct Hamiltonian paths in a given graph, distinguishing it from the decision version by requiring enumeration rather than mere existence. This problem belongs to the complexity class #P, which captures the computational difficulty of counting the accepting paths of a nondeterministic polynomial-time Turing machine. Specifically, counting Hamiltonian paths 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.^[44] A notable reduction establishing this #P-hardness originates from the problem of computing the permanent of a 0-1 matrix, which Valiant also showed to be #P-complete. The construction yields a directed bipartite graph with n row vertices r_1, \dots, r_n and n column vertices c_1, \dots, c_n. Edges exist from r_i to c_j if the matrix entry a_{i j} = 1, and from every c_j to r_{i+1} for i < n. The number of Hamiltonian paths starting at r_1 precisely equals the permanent of the matrix, given by

\perm(A) = \sum_{\sigma \in S_n} \prod_{i=1}^n a_{i, \sigma(i)},

where S_n is the set of permutations of \{1, \dots, n\}. This bijection demonstrates that counting Hamiltonian paths is #P-hard even when restricted to bipartite graphs, 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] as the number of paths that visit exactly the vertices in subset S \subseteq V and end at vertex v \in S. The recurrence is dp[S] = \sum_{\substack{u \in S \setminus \{v\} \\ (u, v) \in E}} dp[S \setminus \{v\}], with base case dp[\{v\}] = 1 for each v. Computing this for all subsets and vertices yields the total count by summing over all possible ending vertices for S = V, achieving time complexity O(2^n n^2) and space O(2^n n). This approach, while exponential, provides the fastest known exact method for moderate n. Applications of counting Hamiltonian paths appear in probabilistic graph theory, particularly for analyzing random graphs. For instance, the expected number of Hamiltonian paths in a random graph G(n, p) with edge probability p can be computed using linearity of expectation over all possible vertex orderings, where each potential path contributes p^{n-1}. If this expectation exceeds 1, the probabilistic method 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 routing data between processing cores in multi-core processors, enabling adaptive communication schemes that minimize latency and avoid deadlocks. These paths are particularly effective in mesh topologies, where they provide a systematic ordering of nodes to facilitate wormhole routing, allowing packets to traverse alternative routes without congestion. For instance, Hamiltonian-based odd-even turn models have been developed to maximize adaptivity in 2D mesh NoCs, outperforming deterministic methods by distributing traffic more evenly across the interconnect.^[45] This approach ensures efficient resource utilization in high-performance computing systems, where latency reduction is critical for overall chip performance.^[46] 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.^[47] By guaranteeing a cycle that visits all modules exactly once, it ensures complete coverage while maintaining electrical integrity.^[48] Research from the 2000s, published in IEEE proceedings, highlighted NoC topologies like torus graphs that inherently guarantee Hamiltonian paths, supporting scalable and fault-tolerant routing in emerging multi-core architectures. Torus structures, with their wrap-around connections, facilitate cycle-based embeddings that enable efficient broadcasting and multicast operations without virtual channels. For example, algorithms for torus-embedded hypercubes were proposed to enhance interconnect performance in parallel systems.^[49] These findings laid the groundwork for deadlock-free protocols in wormhole-routed networks.^[50] 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.^[51] Separately, artificial intelligence is being integrated into quantum chip design to optimize layouts and connectivity, combining machine learning with nanotechnology and semiconductors.^[52]

Computational Geometry and Graphics

In computer graphics, 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.^[53] This approach is particularly useful in autonomous systems where computational resources limit exhaustive searches, providing a near-optimal traversal of viewpoints derived from surface normals or feature points. Additionally, Hamiltonian paths facilitate triangle stripification in mesh rendering, where the dual graph of a triangulated surface is traversed to produce continuous strips of triangles, 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.^[54] In printed circuit board (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.^[55] This geometric routing ensures collision-free traversals in the layout plane, aligning with computational geometry principles for planar graphs. The art gallery problem in computational geometry relates to Hamiltonian paths through visibility graphs, where vertices represent polygon corners and edges indicate mutual visibility. Visibility graphs of simple polygons always contain a Hamiltonian cycle formed by the boundary edges. Under certain conditions, such as when endpoints form disjoint segments, a Hamiltonian path 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.^[56]^[57] Hamiltonian paths appear in robot motion planning for collision-free traversals, particularly in constrained environments like polygonal obstacles. For snake-like robots, which must maneuver without self-intersection, the problem reduces to finding a Hamiltonian path in a configuration graph of joint positions, proven PSPACE-complete 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.^[58] Recent applications in virtual reality (VR) and augmented reality (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.^[53]

Biological and Optimization Contexts

The Hamiltonian path problem finds significant application in bioinformatics, particularly in genome assembly, where reconstructing a DNA sequence from short, overlapping reads is formulated as identifying a Hamiltonian path in an overlap graph. In this model, each read represents a vertex, and edges connect vertices based on the overlap between reads; a Hamiltonian path through all vertices corresponds to the original sequence by aligning the overlaps without repetition. This approach, central to the overlap-layout-consensus (OLC) paradigm, was highlighted in foundational work on computational molecular biology, though practical implementations often approximate the NP-hard path due to graph complexity.^[59]^[60] 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.^[61]^[62] 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.^[63] 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 production planning. Heuristic methods, such as branch-and-bound variants, are commonly applied for large-scale instances due to the problem's intractability.^[64]^[65] In logistics, approximations to the Hamiltonian path appear in vehicle routing problems (VRP), particularly open variants where routes start from a depot and end at a customer without returning, effectively seeking a path covering all demand points with capacity constraints. Clustered routing formulations use Hamiltonian paths to order visits within customer groups, reducing total travel distance; approximation algorithms achieve ratios near 3/2 for such cases, enabling scalable solutions for fleet management. These models extend to heterogeneous fleets, where vehicle types influence path feasibility.^[66]^[67]

References

[1]
Hamiltonian Path -- from Wolfram MathWorld
A Hamiltonian path, also called a Hamilton path, is a graph path between two vertices of a graph that visits each vertex exactly once.
[2]
[PDF] NP-Complete Problems 1 Definitions - MIT OpenCourseWare
Apr 10, 2015 · Hamiltonian Path Given a directed graph G = (V, E), is there a path that visits every vertex exactly once? Given that Hamiltonian Cycle is NP- ...
[3]
Hamiltonian Cycle -- from Wolfram MathWorld
In general, the problem of finding a Hamiltonian cycle is NP-complete (Karp 1972; Garey and Johnson 1983, p. 199), so the only known way to determine ...
[4]
[PDF] Hamiltonian Path is NP-Complete
Mar 5, 2020 · A graph G has a Hamiltonian path from s to t if there is an s to t path that visits all of the vertices exactly once.
[5]
[PDF] REDUCIBILITY AMONG COMBINATORIAL PROBLEMS
DIRECTED HAMILTON CIRCUIT < UNDIRECTED HAMILTON CIRCUIT was pointed out by Tarjan. Below we list three problems in automata theory and language theory to which ...
[6]
[PDF] 1 Hamiltonian Path - People | MIT CSAIL
Nov 2, 2020 · We'll see algorithms for the case of k = n (Hamiltonian Path) and then we'll turn to. “parameterizing” these algorithms so they work for all k.
[7]
Graph Theory | SpringerLink
Oct 29, 2021 · A Hamiltonian path in a graph is a path that visits every vertex once and once only. Hamiltonian paths are applicable to the travelling salesman ...9.2 Undirected Graphs · 9.2. 1 Hamiltonian Paths · 9.5 Graph Colouring And...
[8]
[PDF] Hamiltonian path and Hamiltonian cycle are solvable in polynomial ...
Apr 1, 2025 · Karp [28] proved already in 1972 that deciding the existence of Hamiltonian paths ... An optimization version of the Hamiltonian path problem is ...
[9]
[PDF] Reducibility among Combinatorial Problems
Karp's paper showed that computational intractability is the rule rather than the exception. • Together Cook & Karp, and independently Levin laid the.
[10]
[PDF] NP-completeness
Claim: G has a Hamilton Cycle if and only if G′ has a Hamilton Path. If G has a Hamiltonian cycle, without loss of generality, suppose the cycle is v1 → v2 → ⋯ ...
[11]
[PDF] CMSC 451: SAT, Coloring, Hamiltonian Cycle, TSP
Now any Hamiltonian Path must start at v0 and end at v00. G00 has a Hamiltonian Path ⇐⇒ G has a Hamiltonian Cycle. =⇒ If G00 has a Hamiltonian Path, then the ...
[12]
(PDF) Reducibility Among Combinatorial Problems - ResearchGate
We show that a large number of classic unsolved problems of covering, matching, packing, routing, assignment and sequencing are equivalent.
[13]
[PDF] Even More Reductions CSE 417 Winter 21 - Washington
On a directed graph G: A Hamiltonian Path is a path that visits every vertex exactly once. A Hamiltonian Cycle is a Hamiltonian Path with an extra edge.
[14]
Leonard Euler's Solution to the Konigsberg Bridge Problem
Euler's Proof. On August 26, 1735, Euler presented a paper containing the solution to the Konigsberg bridge problem. He addressed both this specific problem ...
[15]
Introducing Knight's Tours - Mayhematics
The earliest surviving knight's tour that can be given a reasonably definite date is this one by al-Adli ar-Rumi, who flourished in Baghdad around 840.
[16]
[PDF] Knight's Tour - How Euler Did It
Euler wrote this in the early 1750's, a time when a chess fad swept the courts of Europe. In 1751 the great chess master and good composer François-André ...
[17]
[PDF] ACCOUNT OF THE ICOSIAN CALCULUS By William Rowan Hamilton
By Sir William R. Hamilton. Communicated November 10, 1856. [Proceedings of the Royal Irish Academy, vol. 6 (1858), p. 415–416.] Sir William Rowan Hamilton ...Missing: game 1857
[18]
The `Icosian Calculus' - Trinity College Dublin
He published short papers describing the Icosian Calculus in the Philosophical Magazine for 1856, and in the Proceedings of the Royal Irish Academy. Hamilton ...
[19]
[PDF] On the history of combinatorial optimization (till 1960) - CWI
Combinatorial optimization is relatively young, with independent research lines until the 1950s when linear programming unified them. The assignment problem ...
[20]
Ore's Theorem -- from Wolfram MathWorld
"Note on Hamilton Circuits." Amer. Math. Monthly 67, 55, 1960. Palmer, E. M. "The Hidden Algorithm of Ore's Theorem on Hamiltonian Cycles." Computers Math. Appl ...Missing: path | Show results with:path
[21]
[PDF] A Study of Sufficient Conditions for Hamiltonian Cycles
Theorem 1.2 (Ore, 1960, [24]): If G is a graph of order n ≥ 3 such that for all distinct nonadjacent pairs of nodes u and v, deg (u) + deg (v) ≥ n, then G is ...
[22]
A historical note on the 3/2-approximation algorithm for the metric ...
Christofides (1976) presented an O ( n 3 ) -time 3/2-approximation algorithm for this special case: it yields a tour that is at most 3/2 times longer than the ...
[23]
[PDF] Improving Christofides' Algorithm for the s-t Path TSP - Theory @ EPFL
Christofides (1976) gave a 3/2-approximation algorithm. Definition. A ρ ... endpoints s, t ∈ V, find a minimum s-t Hamiltonian path. Triangle inequality ...Missing: relation | Show results with:relation
[24]
Quantum Algorithm for Linear Systems of Equations | Phys. Rev. Lett.
A quantum algorithm that uses the solution to a set of linear equations provides an exponential speedup by comparison with classical alternatives.Missing: path | Show results with:path
[25]
[PDF] Finding Long Directed Cycles Is Hard Even When DFVS Is Small or ...
Abstract. We study the parameterized complexity of two classic problems on directed graphs: Hamiltonian. Cycle and its generalization Longest Cycle.
[26]
The Longest (s, t)-Path Problem on O-Shaped Supergrid Graphs
Jun 15, 2023 · In this paper, we will determine the complexity of the longest ( s , t ) -path problem on O-shaped supergrid graphs, which form a subclass of supergrid graphs ...<|separator|>
[27]
https://www.cs.toronto.edu/~ashe/ham-path-notes.pdf
[28]
Finding Long Directed Cycles Is Hard Even When DFVS Is Small Or ...
Aug 11, 2023 · Since 2008, it is known that Hamiltonian Cycle is W[1]-hard when parameterized by directed treewidth [Lampis et al., ISSAC'08].
[29]
Solving Connectivity Problems Parameterized by Treewidth in ...
Solving Connectivity Problems Parameterized by Treewidth in Single ... Hamiltonian Path, Steiner Tree, Feedback Vertex Set and Connected Dominating Set.
[30]
QUBO formulations of the longest path problem - ScienceDirect.com
Apr 8, 2021 · The longest path problem is NP-hard. This paper presents two QUBO formulations: one based on assigning positions and another using degree ...
[31]
A Dynamic Programming Approach to Sequencing Problems
We design a deterministic algorithm that finds a universal scheduling sequence with a solution value within 4 times the value of an optimal clairvoyant ...
[32]
Backtracking (the) Algorithms on the Hamiltonian Cycle Problem
Jul 1, 2021 · In this paper, we make a unified large scale quantitative comparison for the best known backtracking algorithms described between 1877 and 2016.
[33]
hamiltonian_path | OR-Tools - Google for Developers
Aug 6, 2024 · The advantage of the Held and Karp formulation is that it enables: - to build the dynamic programming lattice layer by layer starting from the ...<|control11|><|separator|>
[34]
[PDF] hamiltonian path
Reduction of hamiltonian path to sat. • Given a graph G, we shall construct a CNF R(G) such that R(G) is satisfiable iff G has a Hamiltonian path. • R(G) has ...
[35]
[PDF] Encoding the Hamiltonian Cycle Problem into SAT Based on Vertex ...
This paper presents a SAT encoding, called vertex elimination encoding (VEE), for the Hamiltonian. Cycle Problem (HCP). The encoding maps a Hamiltonian cycle in ...
[36]
Hamiltonian Cycle as an integer linear programming problem
Feb 26, 2013 · The goal is: min∑(u,v)∈Ex(u,v) · For every vertex v, it can have exactly two edges connecting it:∑v∈Vx(u,v)=2. · The Hamiltonian cycle satisfies ...
[37]
[PDF] Algorithmic QUBO Formulations for k-SAT and Hamiltonian Cycles
Apr 28, 2022 · Thus, a solution x consists of the position numbers in the cycle for all directed edges of the graph. Each position number is represented.Missing: integer | Show results with:integer
[38]
[PDF] Hamiltonian Paths in Directed Graphs
Proof * learly membership in this language can be verified in polynomial time given a certificate consisting of a list of all nodes different from s and t ...
[39]
[PDF] chapter 7 / time complexity
A brute-force algorithm for PATH proceeds by examining all potential parts in G and determining whether any is a directed path from s to t. A potential pa is a ...
[40]
[PDF] Time Complexity Checking vs. Proving vs. Disproving Polynomial ...
Mar 20, 2019 · Def. NP is the class of languages that have polynomial-time verifiers. For HAMPATH, the certificate can be simply the path.
[41]
Improving hamiltonian-based routing methods for on-chip networks
Mar 24, 2014 · The Hamiltonian-based odd-even turn model for maximally adaptive routing in 2D mesh networks-on-chip.
[42]
[PDF] Improving Hamiltonian-based Routing Methods for On-chip Networks
Compared to the deterministic routing schemes, adaptive routing methods achieve better per- formance by sending the packets through alternative paths, and.
[43]
Laying the power and ground wires on a VLSI chip
Using a Hamiltonian cycle to divide the chip into regions PI's power-routing phase divides the chip into a VDD region and a GND region and then routes each net ...
[44]
[PDF] Routing the Power and Ground Wires on a VLSI Chip - DSpace@MIT
May 25, 1984 · Keeping the two trees from crossing by drawing a Hamiltonian cycle through the modules, routing one tree inside and the other outside the cycle.
[45]
Hybrid Approach for Discovering k-Hamiltonian Paths in a Torus ...
The objective of this study is to devise a methodology for identifying k-Hamiltonian paths in an extensive TREB network. Contributions include theoretical and ...<|separator|>
[46]
Hamiltonian-cycle-based multicasting on wormhole-routed torus ...
In this paper, we propose an efficient multipath multicast routing algorithm in wormhole-routed 2D torus networks. We first introduce a hamiltonian cycle model ...
[47]
QCE25 Technical Papers Albuquerque Convention Center August 31
Hybrid and Quantum Graph Algorithms via Quantum Array Search: Applications to Hamiltonian Paths and Path. Counting — Ethan Hunt, Hieu ...
[48]
(PDF) AI-Driven Quantum Chip Design: Integrating Semiconductors ...
Jun 30, 2025 · This book explores the multidisciplinary convergence of quantum computing, semiconductor engineering, nanotechnology, and artificial ...<|control11|><|separator|>
[49]
[PDF] One-Shot View Planning for Fast and Complete Unknown Object ...
Apr 3, 2023 · The shortest Hamiltonian path is a Hamiltonian path with minimized ... Jo, “Online coverage and inspection planning for 3d modeling,” Autonomous ...
[50]
[PDF] Hamiltonian Triangulations and Triangle Strips
Graph theory defines a Hamiltonian path as a path that contains each ver- tex of a graph exactly once [Clark, Holton, 1991, p. 99]. Using that, we can define a ...
[51]
[PDF] The assembly of printed circuit boards: a case with multiple ... - ORBi
Dec 22, 1998 · We compute, for every pair of feeders, a value which equals the length of a Hamiltonian path through these locations, thereby utilizing the fact ...
[52]
[PDF] ART GALLERY THEOREMS AND ALGORITHMS
It is an interesting open question to see if the problem of finding a. Hamiltonian cycle in a visibility graph remains intractable. Given this uncertainty ...
[53]
[PDF] Segment Endpoint Visibility Graphs are Hamiltonian* - Ethz
A Hamiltonian polygon is a simple polygon whose vertices are exactly the endpoints of the line segments and whose sides correspond to edges of Vis(S).
[54]
https://www.palfrader.org/research/misc/2011-tristrips.pdf
[55]
Information-optimal genome assembly via sparse read-overlap graphs
A fundamental challenge in assembling from a read-overlap graph is that the true sequence corresponds to a Hamiltonian path on the graph, and, under most ...
[56]
[PDF] An Eulerian path approach to DNA fragment assembly - Brown CS
This paper suggests an approach to the fragment assembly problem based on the notion of the de Bruijn graph. In an informal way, one can visualize the ...
[57]
Study on Protein Structure Based on Reverse Hamilton Path Models
Aug 6, 2025 · Protein structure prediction (PSP) aims to reconstruct the 3D structure of a given protein starting from its primary structure (chain of amino ...
[58]
[PDF] A Hamilton Path-Based Approach to DNA Sequence Analysis
Hamiltonian paths are closely related to another concept in graph theory, "Hamiltonian cycles." While a Hamiltonian path visits each vertex exactly once and.<|separator|>
[59]
[PDF] Hamiltonian Path Problems in the On–line Optimization of Flexible ...
Apr 6, 2011 · ... VR ∪ VS and |VR| = |VS| = k. The nodes in VS correspond to “service ... considered in Ar. If the reserve–graph–pricing was successful ...
[60]
A Cutting Plane Approach to the Sequential Ordering Problem (with ...
The sequential ordering problem (SOP) finds a minimum cost Hamiltonian path subject to certain precedence constraints. The SOP has a number of practical ...
[61]
Hamiltonian paths in large clustered routing problems - ResearchGate
In this paper we discuss the shortest pre-Hamiltonian path problem, and argue that this problem provides a good basis to determine the order in which to visit ...
[62]
Approximation Algorithm for a Heterogeneous Vehicle Routing ...
Jan 1, 2015 · This article addresses a fundamental path planning problem which aims to route a collection of heterogeneous vehicles such that each target ...
[63]
[PDF] COVID-19 Contact Tracing Application Model Using Graph Theory
The presence of a Hamiltonian path or circuit in a contact tracing model suggests that all nodes. (people) that took place in the contact tracing are subject to ...