Hamiltonian Path & Cycle
A Hamiltonian Path visits every vertex of a graph exactly once (a Hamiltonian Cycle returns to the start), an NP-complete problem solved exactly in O(2^n * n^2) via Bitmask DP for n <= 20.
Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code
Hamiltonian Path & Cycle
A Hamiltonian Path visits every vertex of a graph exactly once; a Hamiltonian Cycle additionally returns to the starting vertex. Unlike an Eulerian Path (which visits every edge once in $O(V + E)$), deciding whether a Hamiltonian Path/Cycle exists is NP-complete—solved exactly for $n \le 20$ in $O(2^n \cdot n^2)$ via Bitmask DP!
Practice Problems
Hard
1. Check Existence of a Hamiltonian Cycle via Bitmask DP
Determine whether an undirected graph has a Hamiltonian Cycle (visiting all $n$ vertices once and returning to vertex 0).
Approach: dp[mask][u] = true if there is a path starting at 0, visiting mask, and ending at u. A Hamiltonian Cycle exists iff some u has dp[(1 << n) - 1][u] == true AND edge (u, 0) exists! Time: $O(2^n \cdot n^2)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <vector>
bool hasHamiltonianCycle(int n, const std::vector<std::vector<int>>& adj) {
int full = 1 << n;
std::vector<std::vector<bool>> dp(full, std::vector<bool>(n, false));
dp[1][0] = true;
for (int mask = 1; mask < full; ++mask) {
for (int u = 0; u < n; ++u) {
if (!dp[mask][u]) continue;
for (int v : adj[u]) {
if (!(mask & (1 << v))) dp[mask | (1 << v)][v] = true;
}
}
}
for (int u = 1; u < n; ++u) {
if (!dp[full - 1][u]) continue;
for (int v : adj[u]) if (v == 0) return true;
}
return false;
}
int main() {
std::vector<std::vector<int>> cycle4 = {{1, 3}, {0, 2}, {1, 3}, {2, 0}};
std::vector<std::vector<int>> star4 = {{1, 2, 3}, {0}, {0}, {0}};
std::cout << std::boolalpha << hasHamiltonianCycle(4, cycle4) << " "
<< hasHamiltonianCycle(4, star4) << "\n"; // true false
return 0;
}
</details>
---
Related Algorithms
- Bitmask DP — Held–Karp TSP and Hamiltonian path counting.