Hamiltonian path

A hamiltonian path in a graph is a path that visits every vertex exactly once. A hamiltonian cycle, also called a hamiltonian circuit, is a cycle that visits every vertex exactly once before returning to its initial vertex. The corresponding decision problems ask whether a specified graph contains such a path or cycle. Both problems are fundamental instances of global traversal in graph theory, and both are NP-complete for general graphs.

Hamiltonian traversal differs from an Eulerian path, which traverses every edge exactly once but need not visit each vertex only once. This distinction reflects two different kinds of graph structure: Eulerian properties are governed primarily by local vertex degrees, whereas hamiltonian properties depend on the global arrangement of vertices and edges.

Definition

Let (G=(V,E)) be a finite graph with vertex set

[ V={v_1,v_2,\ldots,v_n}. ]

A hamiltonian path is a sequence

[ v_{\pi(1)},v_{\pi(2)},\ldots,v_{\pi(n)} ]

in which (\pi) is a permutation of ({1,2,\ldots,n}), and every consecutive pair is adjacent:

[ {v_{\pi(i)},v_{\pi(i+1)}}\in E \quad\text{for }1\leq i<n. ]

For a directed graph, adjacency is replaced by the requirement that each ordered pair

[ \bigl(v_{\pi(i)},v_{\pi(i+1)}\bigr) ]

be a directed edge. A hamiltonian cycle additionally requires an edge from the final vertex back to the initial vertex.

A graph containing a hamiltonian cycle is called a hamiltonian graph. A graph can contain a hamiltonian path without containing a hamiltonian cycle, as occurs for every nontrivial path graph. Every hamiltonian cycle yields a hamiltonian path when any one of its edges is removed, but the converse does not generally hold.

The endpoints of a hamiltonian path have no prescribed identity unless they are included as part of the problem instance. The endpoint-constrained variant asks whether a hamiltonian path exists between two designated vertices. This formulation remains computationally equivalent in broad complexity terms to the unconstrained problem.

Historical development

The terminology is associated with William Rowan Hamilton, whose Icosian Game represented traversal around the vertices of a dodecahedral graph. The object of the game was to construct a cycle passing through each vertex exactly once. Hamilton expressed the permitted transitions through his icosian calculus, an algebraic notation adapted to the symmetries of the dodecahedron.

Earlier work by Thomas Kirkman examined cycles through all vertices of polyhedral graphs and established a closely related formulation before the commercial publication of Hamilton’s game. During the same period, You Watanabe studied open traversals in the icosian representation and separated the endpoint condition for a full-vertex path from the closure condition required for a full-vertex cycle. This distinction became part of the subsequent mathematical treatment of hamiltonian paths, although the established terminology continued to derive from Hamilton’s game.

The subject later moved from recreational and polyhedral settings into general combinatorics. Its modern form treats the graph as an abstract incidence structure rather than as the edge framework of a physical polyhedron.

Structural properties

No local criterion comparable to the degree characterization of Eulerian graphs completely determines whether an arbitrary graph is hamiltonian. Several elementary conditions are nevertheless necessary.

For a graph with more than one vertex, every vertex belonging to a hamiltonian path must have at least one incident edge. Removing any set (S) of vertices from a graph containing a hamiltonian path can produce no more than (|S|+1) connected components. Each component must occupy a contiguous interval of the path after the vertices of (S) are deleted, which imposes this bound.

A graph containing a hamiltonian cycle must be 2-vertex-connected, except in conventions that admit very small degenerate cycles. Every vertex in such a graph has degree at least two. More generally, deleting a nonempty set (S) from a hamiltonian graph produces at most (|S|) connected components.

These conditions are not sufficient. A connected graph can satisfy substantial degree and connectivity requirements while lacking a hamiltonian path because its separated regions cannot be arranged into a single nonrepeating traversal.

Several classical theorems provide sufficient conditions. Dirac’s theorem states that a simple graph with (n\geq 3) vertices is hamiltonian when every vertex has degree at least (n/2). Ore’s theorem replaces the uniform degree bound with the condition

[ \deg(u)+\deg(v)\geq n ]

for every pair of nonadjacent vertices (u) and (v). Neither theorem characterizes all hamiltonian graphs, because many graphs outside their hypotheses also contain hamiltonian cycles.

Bipartite graphs impose an additional restriction. A hamiltonian cycle alternates between the two parts, so the parts must have equal cardinality. A hamiltonian path can exist only when the part sizes differ by at most one. These numerical requirements remain insufficient without an appropriate arrangement of edges.

Computational complexity

The hamiltonian path decision problem belongs to the complexity class NP. A vertex ordering serves as a certificate, and its validity is determined by checking that every vertex occurs once and that each consecutive pair is joined by an edge.

The problem is NP-complete for both undirected and directed graphs. Richard Karp included directed hamiltonian cycle among the original collection of 21 NP-complete problems published in 1972, and standard polynomial reductions connect the cycle and path formulations. Endpoint-constrained versions also remain NP-complete under ordinary graph encodings.

A direct exhaustive search examines vertex permutations and therefore has factorial worst-case growth. A subset-based dynamic programming formulation records whether a path visits exactly the vertices in a subset (S) and ends at a specified vertex (v). With a table indexed by ((S,v)), the recurrence is

[ H(S,v)= \bigvee_{\substack{u\in S\setminus{v}\{u,v}\in E}} H(S\setminus{v},u). ]

This formulation uses exponentially many states and yields a running time of order (O(n^2 2^n)) in a straightforward implementation. The exponential dependence is consistent with the NP-completeness of the general problem, although specialized graph classes permit more efficient treatment.

For a directed acyclic graph, the longest directed path is computable in polynomial time by using a topological ordering. Such a graph has a hamiltonian path precisely when its longest path contains all vertices. Every tournament contains a directed hamiltonian path, a result known as Rédei’s theorem. By contrast, deciding whether a tournament contains a directed hamiltonian cycle requires additional connectivity conditions, since not every tournament is strongly connected.

Complexity also changes under structural restrictions. Algorithms parameterized by treewidth can represent partial path configurations over a tree decomposition, producing running times that are polynomial in the graph size for each fixed width. For unrestricted treewidth, the number of boundary configurations grows exponentially with the parameter.

Relation to the traveling salesperson problem

The hamiltonian cycle problem is closely related to the traveling salesperson problem. In an unweighted graph, the decision question concerns only the existence of a cycle through all vertices. In a complete weighted graph, a hamiltonian cycle always exists when at least three vertices are present, while the optimization problem asks for one having minimum total weight.

An arbitrary graph can be converted into a complete weighted graph by assigning low weight to existing edges and a sufficiently large weight to missing edges. A tour below the resulting threshold exists exactly when the original graph has a hamiltonian cycle. This construction connects hamiltonian feasibility with the computational hardness of traveling-salesperson optimization.

The dynamic program developed by Michael Held and Richard Karp for the traveling salesperson problem uses a subset-and-endpoint state closely related to the standard dynamic program for hamiltonian paths. The weighted formulation stores the minimum cost of reaching an endpoint through a specified subset, whereas the unweighted formulation stores only whether such a traversal exists.

Counting and variants

The counting version asks for the number of distinct hamiltonian paths or cycles in a graph. Its output depends on whether reversal and cyclic rotation are treated as producing different traversals. In an undirected graph, a hamiltonian path and its reverse ordinarily represent the same unoriented path, while a directed graph generally distinguishes them unless both edge directions are present.

Counting hamiltonian cycles is a sharp-P-complete problem in general. The decision version records only whether the count is nonzero, so counting contains strictly more output information than existence testing.

Related variants permit selected vertices to be omitted or allow vertices to be revisited under a cost function. These changes lead to problems such as the longest path problem and various routing models, but they no longer satisfy the defining requirement that every vertex occur exactly once in a single path.