Hamiltonian Path and Circuit Problems

A Hamiltonian path in a graph $G = (V, E)$ is a path that visits every vertex in $V$ exactly once (no repeats, no omissions). A Hamiltonian circuit (or Hamiltonian cycle) is a Hamiltonian path that additionally has an edge from the last vertex back to the first, forming a closed tour. The decision problems are:

Both problems are naturally in NP: given a proposed vertex ordering as a certificate, checking that it is a permutation of $V$ and that consecutive vertices are joined by edges of $G$ takes only $O(|V| + |E|)$ time. The entire difficulty is in the search — with $n$ vertices there are up to $n!$ orderings to consider, and no polynomial-time method is known (or believed to exist) to avoid this combinatorial explosion in the worst case. The hardness half of the NP-completeness proof uses a polynomial-time many-one reduction from 3-SAT, written $\text{3-SAT} \leq_p \text{HAMPATH}$. This means we give an algorithm that, given any 3-CNF formula $\phi$, runs in time polynomial in $|\phi|$ and outputs a graph $G$ (with designated start and end vertices) such that

Since 3-SAT is NP-complete by the Cook–Levin theorem (via the standard SAT-to-3-SAT reduction), and since this reduction is computable in polynomial time, HAMPATH inherits NP-hardness. Combined with membership in NP, this proves HAMPATH is NP-complete. The technique of building small local structures — gadgets — that simulate variables and clauses is the same craft used for Clique, Vertex Cover, Independent Set, and dozens of other NP-completeness proofs; mastering it here transfers directly to those settings.

The gadget construction

Fix a 3-CNF formula $\phi$ with variables $x_1, \dots, x_n$ and clauses $c_1, \dots, c_m$, each clause a disjunction of exactly three literals. We build a directed graph $G$ as follows.

Variable gadgets (diamonds). For each variable $x_i$, construct a horizontal chain of $2m$ vertices between two endpoint vertices, arranged as a "diamond" — really a pair of parallel row structures with $2m$ intermediate nodes each — such that:

• The diamond can be traversed left-to-right using the top row, corresponding to setting $x_i = \text{TRUE}$.
• The diamond can be traversed right-to-left using the bottom row, corresponding to setting $x_i = \text{FALSE}$.
• Crucially, each of the $2m$ positions in the row corresponds to one of the $2m$ clause-slots (each clause can mention $x_i$ positively or negatively, so there are up to $2m$ relevant occurrences, one slot reserved per clause per polarity).

Chain the $n$ diamonds together end to end: the right endpoint of diamond $i$ connects to the left endpoint of diamond $i+1$ (and also the reverse edge exists, of a special "bridge" form described below), so that a Hamiltonian path must pass through the diamonds in sequence, entering diamond $i$ from one side and leaving from the other, with the direction of traversal free to choose independently per diamond — this freedom is exactly a truth assignment.

Clause gadgets (hub vertices). For each clause $c_j = (\ell_1 \vee \ell_2 \vee \ell_3)$, create a single vertex $c_j$. This vertex needs incoming and outgoing edges from exactly the vertices representing "this literal is satisfied by the current traversal direction of its variable's diamond." Concretely, each diamond has, for every clause it appears in, a small pair of extra edges that detour through $c_j$ if and only if the diamond is traversed in the direction making that literal true. The clause vertex has degree bounded by $6$ (at most three literals, each contributing an in/out detour pair), so checking or constructing it takes constant work per clause.

Global start and end. Add a designated start vertex $s$ feeding into the first diamond and an end vertex $t$ receiving from the last diamond. The essential engineering fact, which must be verified carefully, is: > A Hamiltonian path from $s$ to $t$ must pass through each variable diamond in one single consistent direction (it cannot enter and exit the diamond multiple times without skipping or repeating vertices), and it may detour to pick up a clause vertex $c_j$ only while passing a diamond segment corresponding to a literal of $c_j$ that is true under the direction chosen. This is the crux gadget-design invariant, proved in the Complexity & Correctness section below.

Algorithm: constructing the reduction

``` function REDUCE-3SAT-TO-HAMPATH(phi):

# phi has variables x_1..x_n and clauses c_1..c_m, each with exactly 3 literals G = empty directed graph

# 1. Build one diamond gadget per variable for i in 1..n: D[i] = build_diamond_gadget(variable = x_i, num_clauses = m) add D[i].vertices and D[i].internal_edges to G

# 2. Chain diamonds together with bridging vertices allowing

# left-to-right or right-to-left entry into the next diamond for i in 1..n-1: add_bridge_edges(D[i].right_end, D[i+1].left_end, G)

# 3. Add global start/end s = new vertex; t = new vertex add_edge(s, D[1].left_end, G) add_edge(D[n].right_end, t, G)

# 4. Build one hub vertex per clause and wire literal detours for j in 1..m: c_j = new vertex add c_j to G for each literal L in clause_j: i = variable_index(L) slot = reserved_slot(D[i], clause_j, polarity(L)) wire_detour(D[i], slot, c_j, G) # in-edge and out-edge through c_j return (G, s, t) ``` ``` function wire_detour(diamond, slot, clause_vertex, G):

# 'slot' identifies a pair of consecutive vertices (u, v) on the

# row of 'diamond' corresponding to the literal's true-making direction (u, v) = slot.vertex_pair remove_edge(u, v, G) # direct edge is replaced by detour option add_edge(u, clause_vertex, G) add_edge(clause_vertex, v, G) add_edge(u, v, G) # also keep the direct edge, so the

# path MAY skip the clause vertex if

# it is already satisfied elsewhere ``` The `wire_detour` step is the delicate part: each slot offers the traversing path a choice — take the direct edge $u \to v$, or detour through $c_j$ and then continue $c_j \to v$. Because $c_j$ must be visited exactly once by the final Hamiltonian path (it is a vertex of $G$), it will be "claimed" by exactly one of its offered detours, corresponding to exactly one satisfied literal (though semantically any of the true literals could serve, the Hamiltonian-path property only forces at least one opportunity to succeed).

Diagram

Reading the figure: the path enters diamond $x_1$ at its left tip, and can go via the top row (setting $x_1 = \text{TRUE}$) or the bottom row ($x_1 = \text{FALSE}$). If it uses the top row, it passes near the orange clause vertex $c_1$ and may detour to visit it (since $x_1$ appears positively in $c_1$). The path then crosses the black bridge vertex into diamond $x_2$, and so on, finally reaching $t$. Every clause vertex must be picked up by some detour for the tour to be Hamiltonian — this is exactly the constraint that the corresponding clause be satisfied.

Size and time bound. For $n$ variables and $m$ clauses, each diamond gadget has $O(m)$ vertices (one slot pair per clause occurrence, and each variable occurs in at most $3m$ literal slots across all clauses, but standard constructions bound this by $O(m)$ per diamond by reusing slots per clause rather than per literal occurrence). There are $n$ diamonds and $m$ clause vertices, giving

and the construction algorithm processes each clause and variable slot in constant time per edge, so REDUCE-3SAT-TO-HAMPATH runs in time $O(nm)$, which is polynomial in $|\phi|$. This satisfies the requirement for a valid Karp reduction: the transformation itself must be computable by a deterministic polynomial-time algorithm, independent of whether HAMPATH itself is efficiently solvable.

Membership in NP. A certificate for $\langle G, s, t \rangle \in \text{HAMPATH}$ is simply the sequence of vertices $v_1 = s, v_2, \dots, v_k = t$ claimed to be a Hamiltonian path. Verification checks (a) the sequence is a permutation of $V(G)$ — sort and compare, $O(|V| \log |V|)$ — and (b) each consecutive pair $(v_i, v_{i+1})$ is an edge of $G$ — a hash-set lookup per pair, $O(|V|)$ total. Both run in time polynomial in the input size, so HAMPATH $\in$ NP. The same argument, with the added check that $v_k \to v_1 \in E$, shows HAMCYCLE $\in$ NP.

Correctness of the reduction — forward direction. Suppose $\phi$ has a satisfying assignment $\alpha$. Define a path through $G$ that traverses diamond $i$ via the top row if $\alpha(x_i) = \text{TRUE}$ and the bottom row if $\alpha(x_i) = \text{FALSE}$, moving straight through bridge vertices between diamonds, from $s$ to $t$. Since $\alpha$ satisfies $\phi$, every clause $c_j$ has at least one literal made true by $\alpha$; pick one such literal per clause and have the path take the corresponding detour through $c_j$ exactly at that slot (taking direct edges at all other slots). Because each clause vertex is visited exactly once (via its one chosen detour) and every diamond, bridge, and endpoint vertex is visited exactly once by construction, this yields a Hamiltonian path from $s$ to $t$.

Correctness of the reduction — backward direction. Suppose $G$ has a Hamiltonian path $P$ from $s$ to $t$. Because the diamonds are chained in a strict sequence via bridge vertices with no alternate routes between non-adjacent diamonds, $P$ must traverse the diamonds in index order $1, 2, \dots, n$ (any attempt to skip ahead or double back would either strand vertices unreached or revisit a bridge vertex, violating the Hamiltonian property). Within diamond $i$, the internal wiring is designed so that a Hamiltonian path can only enter at one tip and leave at the other by committing to a single row — top or bottom — for the entire diamond; mixing rows mid-diamond would leave some row-vertices unvisited or force a revisit of a shared vertex. (This is the load-bearing combinatorial fact about the diamond's internal structure: it has, by design, no Hamiltonian sub-path traversal pattern other than "all-top" or "all-bottom.") Define $\alpha(x_i) = \text{TRUE}$ if $P$ uses the top row of diamond $i$, else FALSE. Since $P$ is Hamiltonian, every clause vertex $c_j$ lies on $P$, meaning $P$ took some detour through $c_j$ at a slot corresponding to some literal $\ell$ of $c_j$; by the wiring, this detour is only available when the diamond for $\ell$'s variable is traversed in the direction making $\ell$ true. Hence $\ell$ is true under $\alpha$, so clause $c_j$ is satisfied. As this holds for every clause, $\alpha$ satisfies $\phi$. Together, the two directions establish $\phi \in \text{3-SAT} \iff \langle G, s, t\rangle \in \text{HAMPATH}$, completing the reduction and proving HAMPATH is NP-hard. Combined with NP membership, HAMPATH is NP-complete.

Transferring to HAMCYCLE. To show HAMCYCLE is NP-complete, reduce HAMPATH to it: given $\langle G, s, t \rangle$, add a new vertex $z$ with edges $t \to z$ and $z \to s$ (and no other edges touching $z$), producing $G'$. Any Hamiltonian $s\!\to\!t$ path in $G$ extends to a Hamiltonian cycle in $G'$ by appending $t \to z \to s$, and conversely any Hamiltonian cycle in $G'$ must use both edges incident to $z$ (since $z$ has exactly one in-edge and one out-edge), so removing $z$ from the cycle yields a Hamiltonian $s\!\to\!t$ path in $G$. This reduction runs in $O(1)$ extra time and space, so HAMCYCLE is NP-hard, and it is in NP by the same certificate argument, hence NP-complete.

Honest complexity picture. No known algorithm solves HAMPATH or HAMCYCLE in time polynomial in $n = |V|$ in the worst case. The naive brute-force search over all $n!$ orderings is far too slow, but dynamic programming over subsets (Held–Karp style, akin to the technique used for the Traveling Salesman Problem) solves it in $O(2^n \cdot n^2)$ time and $O(2^n \cdot n)$ space — exponential, but a dramatic improvement over factorial brute force, and it remains the best known worst-case bound for general graphs. Special graph classes (e.g., graphs with high minimum degree, per Dirac's and Ore's theorems) admit polynomial-time Hamiltonicity tests or guarantees, illustrating that hardness is a worst-case, not universal, property.

Let $\phi = (x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_1 \vee x_3 \vee x_2)$, with $n = 3$ variables, $m = 2$ clauses, matching the figure above.

Trace of the failed attempt ($\alpha$) shows why the reduction is sound: it is not merely that some Hamiltonian path exists whenever a graph is "big enough" — an inconsistent assignment genuinely fails to produce a valid tour, because clause vertex $c_2$ would have no available detour edge to be entered from and left to, stranding it unreachable within a single Hamiltonian path (any attempted visit to $c_2$ without a valid literal detour would require using an edge that was never wired into the graph, since `wire_detour` only adds edges through $c_j$ for literals appearing in $c_j$). This confirms the backward direction of the correctness proof concretely: an unsatisfying assignment corresponds to no Hamiltonian path, not just a Hamiltonian path that happens not to exist for unrelated reasons.

The Hamiltonian path problem is named for the 19th-century Irish mathematician who studied cycles on the dodecahedron, but its complexity-theoretic significance emerged a century later with the founding of NP-completeness theory.

Vehicle routing and logistics systems that must construct delivery tours touching every stop exactly once are directly modeling Hamiltonian path/circuit search, typically relaxed into the closely related Traveling Salesman Problem with costs, solved in practice via heuristics, branch-and-bound, or integer programming solvers rather than exact exponential search. DNA sequencing pipelines historically framed fragment assembly as a Hamiltonian path problem on an overlap graph before shifting to the polynomial-time-tractable Eulerian path formulation on de Bruijn graphs — a striking real-world case where recognizing the P-vs-NP gap between the two "visit everything once" problems changed algorithm design. Circuit board drilling and 3D printer toolpath optimization also reduce to Hamiltonian-path-like tours minimizing travel between points. In compilers and hardware design, register allocation and certain scheduling problems embed Hamiltonian-path subproblems as hardness certificates justifying the use of heuristic or approximate schedulers instead of exact ones. Pedagogically, the gadget-based 3-SAT-to-HAMPATH reduction remains one of the clearest illustrations of how a single unifying proof technique — variable gadgets plus clause gadgets — powers NP-completeness proofs across graph theory, scheduling, and beyond, directly paralleling the gadget style used for Clique and Vertex Cover.

Ask the tutor: Can you show me exactly how the "diamond" gadget's internal edges rule out a mixed-row traversal, with the full edge list?