1. One-Liner
A Hamiltonian path visits each vertex exactly once; deciding existence is NP-complete — small n uses bitmask DP O(n²·2ⁿ) or backtracking with pruning.
2. The Problem It Solves
TSP relaxations, puzzle graphs (Knight’s tour variant on graphs), theoretical CS completeness examples.
3. The Core Idea
No known polynomial algorithm for general graphs. Held-Karp style DP: dp[mask][v] = reachable using vertices in mask ending at v.
4. How It Works (Step-by-Step)
| Approach | Steps |
|---|---|
| Bitmask DP | dp[1<<u][u]=1; transition if edge v→w extend mask |
| Backtracking | DFS assign order, prune when stuck |
5. Dry Run Example
Complete graph K_n always has Hamiltonian paths. Sparse graphs may have none — DP/backtracking explores.
6. Key Properties
| Property | Value |
|---|---|
| Decision | NP-complete |
| Small n | 2^n DP feasible for n≈20 |
7. Where It Is Used
| Domain | Use |
|---|---|
| TSP | Related optimization |
| Education | Complexity theory |
8. Interview Tips
Never claim polynomial general solution; discuss exponential algorithms and heuristics for large instances.
9. Comparison with Other Algorithms
| Hamiltonian | Eulerian | |
|---|---|---|
| Vertices vs edges | Each vertex once | Each edge once |
| Complexity | NP-hard | Polynomial |
10. Complexity
| -- | -- |
|---|---|
| Exact DP | O(n² · 2ⁿ) time, O(n · 2ⁿ) space |
| Brute force | O(n!) permutations |
Implementation Example (PYTHON)
def hamiltonian_path_exists(n, edges):
adj = [[False]*n for _ in range(n)]
for u, v in edges:
adj[u][v] = adj[v][u] = True
FULL = (1 << n) - 1
dp = [[0]*n for _ in range(1 << n)]
for u in range(n):
dp[1 << u][u] = 1
for mask in range(1 << n):
for u in range(n):
if not dp[mask][u]: continue
for v in range(n):
if not (mask & 1 << v) and adj[u][v]:
dp[mask | 1 << v][v] = 1
return any(dp[FULL][u] for u in range(n))