Hamiltonian Path
Graph traversal concept
A Hamiltonian path is a path through a graph that visits every vertex exactly once, and a Hamiltonian cycle is a Hamiltonian path that additionally returns to its starting vertex, forming a closed loop.
Definition
A Hamiltonian path is a path through a graph that visits every vertex exactly once, and a Hamiltonian cycle is a Hamiltonian path that additionally returns to its starting vertex, forming a closed loop.
Overview
Named after the mathematician William Rowan Hamilton, who studied a related puzzle on the edges of a dodecahedron in 1857, the Hamiltonian path problem asks whether a graph contains a path visiting every vertex exactly once. Unlike the closely-related Eulerian path problem, which is efficiently decidable in linear time, determining whether a Hamiltonian path or cycle exists in a general graph is NP-complete: no known polynomial-time algorithm solves it for all graphs, and it is widely believed no such algorithm exists. Because of this computational hardness, practical algorithms for Hamiltonian path problems rely on exponential-time exact methods (such as backtracking with pruning, or dynamic programming over subsets using the Held-Karp approach in O(2^n * n^2) time) for small to moderately sized graphs, or heuristic and approximation methods for larger instances where an exact answer isn't required. Certain special graph classes admit efficient solutions or guaranteed existence results — for example, Dirac's theorem guarantees a Hamiltonian cycle exists in any graph where every vertex has degree at least n/2. The Hamiltonian path problem is deeply connected to one of the most famous problems in computer science, the Traveling Salesman Problem (TSP), which asks for the minimum-weight Hamiltonian cycle in a weighted, complete graph. This connection makes Hamiltonian path techniques directly relevant to logistics and route optimization, vehicle routing, PCB drilling path optimization, and DNA sequencing strategies that model overlaps between fragments as a Hamiltonian path problem. Because of its NP-completeness, the Hamiltonian path/cycle problem is also a canonical example used to prove other problems NP-complete via polynomial-time reduction.
Key Concepts
- Visits every vertex in a graph exactly once
- A Hamiltonian cycle additionally returns to its starting vertex
- Deciding existence is NP-complete for general graphs
- Distinct from Eulerian paths, which are efficiently decidable
- Solvable exactly via backtracking or Held-Karp dynamic programming for small graphs
- Special graph classes (e.g., via Dirac's theorem) guarantee existence
- Directly related to the Traveling Salesman Problem
- Used as a canonical NP-completeness reduction target
Use Cases
Frequently Asked Questions
From the Blog
Photography to Photoshop: Your Creative Career Path
Turn your love of photography into a thriving design career with these actionable steps.
Read More Certifications & GuidesAWS Certification Path: Which One to Choose
A comprehensive guide to aws certification path: which one to choose — written for learners at every level.
Read More AI & TechnologyThe 2026 AI Engineer Roadmap: Skills, Tools, and Career Path
AI Engineer is one of the fastest-growing roles in tech — and it's more accessible than traditional ML engineering. This guide maps the exact skills, tools, and learning sequence for becoming an AI engineer in 2026, from Python basics to deploying production RAG and agent systems.
Read More