Hamiltonian Walks using Bitmask DP
lolz, jus' chill
Hamiltonian Walk is a common application of Bitmask DP.
The problem is simple:
Given a graph, find the shortest path that visits every vertex exactly once.
We can solve this using:
Bitmasking to store visited vertices.
DP to store the answer for each state.
Let's see how.
Problem Statement
Given a graph with n vertices, find the minimum number of edges needed to visit every vertex exactly once.
You can start from any vertex.
If no such path exists, return -1.
For example:
0 ---- 1 ---- 2
The Hamiltonian path is:
0 → 1 → 2
Answer:
2
Solution Approach
The main problem is that we need to remember which vertices have already been visited.
We can use a bitmask for this.
Bitmask
Suppose:
n = 4
We have vertices:
0, 1, 2, 3
We use one bit for each vertex.
mask = 0101
This means:
Vertex 0 → Visited
Vertex 1 → Not visited
Vertex 2 → Visited
Vertex 3 → Not visited
To check if vertex j is visited:
mask & (1 << j)
To mark vertex j as visited:
mask | (1 << j)
DP State
We define:
dp[mask][u]
This means:
Minimum number of edges needed to visit all vertices in
maskand end at vertexu.
For example:
dp[0101][2]
means:
We have visited vertices
0and2, and we are currently at vertex2.
Why do we need u?
Because knowing only the visited vertices is not enough.
The next move depends on where we are currently standing.
Transition
Suppose we are currently at vertex u.
We can move to any unvisited neighbor v.
So:
newMask = mask | (1 << v);
And:
dp[newMask][v]
= min(dp[newMask][v],
dp[mask][u] + 1);
In recursion, this becomes:
rec(mask, u)
We try every unvisited neighbor.
rec(mask | (1 << v), v)
Base Case
If all vertices have been visited, we are done.
The mask containing all vertices is:
(1 << n) - 1
So:
if (mask == (1 << n) - 1)
return 0;
We return 0 because no more edges are needed.
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
vector<vector<int>> adj;
vector<vector<int>> dp;
int rec(int mask, int u){
if(mask == (1 << n) - 1)
return 0;
if(dp[mask][u] != -1)
return dp[mask][u];
int ans = 1e18;
for(int v : adj[u]){
if((mask & (1 << v)) == 0){
ans = min(ans,
1 + rec(mask | (1 << v), v));
}
}
return dp[mask][u] = ans;
}
void solve(){
cin >> n >> m;
adj.assign(n, {});
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dp.assign(1 << n, vector<int>(n, -1));
int ans = 1e18;
for(int i = 0; i < n; i++){
ans = min(ans, rec(1 << i, i));
}
if(ans == 1e18)
cout << -1 << "\n";
else
cout << ans << "\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Complexity
There are:
2^n masks
For each mask, we have n possible ending vertices.
So the number of states is:
O(n * 2^n)
For each state, we may try up to n vertices.
Therefore:
Time Complexity: O(n² * 2ⁿ)
Space Complexity: O(n * 2ⁿ)
This is why Bitmask DP is generally used when n is small.
Variants of Hamiltonian Walk
Once we understand the basic DP, we can modify it to solve different problems.
The state remains the same:
dp[mask][u]
We only change what we want to calculate.
Variant 1: Shortest Hamiltonian Path from Any City
In the previous problem, we started from vertex 0.
But what if we can start from any vertex?
We just try every vertex as the starting point and take the minimum answer.
Approach
For every vertex start:
Mark
startas visited.Start the DP from
start.Find the minimum cost to visit all vertices.
Pseudocode
ans = INF
for start = 0 to n-1:
current = solve(1 << start, start)
ans = min(ans, current)
return ans
Here:
solve(mask, u)
returns the minimum additional cost to visit all remaining vertices, starting from the current state.
What changed?
Nothing in the DP.
We only changed the starting state.
Variant 2: Count Hamiltonian Paths
Instead of finding the shortest path, suppose we want to count the number of Hamiltonian paths.
For example:
0 ---- 1
| |
| |
3 ---- 2
Starting from 0, there are two Hamiltonian paths:
0 → 1 → 2 → 3
0 → 3 → 2 → 1
We want the answer to be 2.
DP State
dp[mask][u]
Now represents:
Number of ways to visit exactly the vertices in
maskand end at vertexu.
Base Case
If all vertices are visited, we have found one valid Hamiltonian path.
if all vertices are visited:
return 1
Why 1?
Because we have completed one valid path.
Transition
From the current vertex u, try every unvisited neighbor v.
For every such neighbor, count the paths that can be formed after moving to v.
solve(mask, u):
if all vertices are visited:
return 1
ans = 0
for every unvisited neighbor v of u:
newMask = mask | (1 << v)
ans += solve(newMask, v)
return ans
The recurrence is:
$$dp[mask][u] \sum_{\text{valid }v} dp[mask \cup {v}][v]$$
What changed?
In the shortest path problem, we used min.
Here, we use sum.
The state and possible transitions remain the same.
Variant 3: Hamiltonian Cycle
A Hamiltonian cycle is a Hamiltonian path that returns to its starting vertex.
For example:
0 → 1 → 2 → 3 → 0
We visit every vertex exactly once and finally return to 0.
Approach
Fix the starting vertex as 0.
We use the same DP as before.
The only difference is what happens when all vertices have been visited.
In a Hamiltonian path:
All vertices visited → Valid path
In a Hamiltonian cycle:
All vertices visited + Edge back to start → Valid cycle
Pseudocode
solve(mask, u):
if all vertices are visited:
if edge(u, start) exists:
return 1
return 0
ans = 0
for every unvisited neighbor v of u:
newMask = mask | (1 << v)
ans += solve(newMask, v)
return ans
Why fix the starting vertex?
Consider:
0 → 1 → 2 → 0
Starting from 1 gives:
1 → 2 → 0 → 1
These are the same cycle, just rotated.
By fixing the starting vertex, we avoid counting the same cycle multiple times due to rotations.
What changed?
Only the base case.
Instead of checking whether all vertices are visited, we also check whether we can return to the starting vertex.
Variant 4: Maximum Weight Hamiltonian Path
Now suppose every edge has a weight.
For example:
0 --5-- 1 --10-- 2
The total weight of:
0 → 1 → 2
is:
5 + 10 = 15
We want to find the Hamiltonian path with the maximum total weight.
DP State
dp[mask][u]
represents:
Maximum total weight of a path that visits exactly the vertices in
maskand ends atu.
Approach
From the current vertex u, try every unvisited neighbor v.
If the edge has weight w, we add w to the answer.
Pseudocode
solve(mask, u):
if all vertices are visited:
return 0
ans = -INF
for every unvisited neighbor v of u:
newMask = mask | (1 << v)
ans = max(ans,
weight(u, v) + solve(newMask, v))
return ans
The recurrence is:
$$dp[mask][u] = \max_{\text{valid }v} \left( w(u,v) + dp[newMask][v] \right)$$
What changed?
In the shortest path problem:
1 + solve(...)
We add 1 because every edge has unit cost.
Here:
weight(u, v) + solve(...)
We add the actual edge weight.
And instead of min, we use max.
Variant 5: Minimum Weight Hamiltonian Path
This is similar to the previous problem.
Instead of maximizing the total weight, we want to minimize it.
For example:
0 --5-- 1 --10-- 2
The path:
0 → 1 → 2
has total weight:
15
We want the minimum possible total weight among all Hamiltonian paths.
Pseudocode
solve(mask, u):
if all vertices are visited:
return 0
ans = INF
for every unvisited neighbor v of u:
newMask = mask | (1 << v)
ans = min(ans,
weight(u, v) + solve(newMask, v))
return ans
The only difference from the maximum weight problem is:
max → min
Quick Summary
| Problem | What changes? |
|---|---|
| Shortest Hamiltonian Path | Minimize number of edges |
| Path from Any City | Try all starting vertices |
| Count Hamiltonian Paths | Add the number of ways |
| Hamiltonian Cycle | Check edge back to start |
| Maximum Weight Path | Maximize total weight |
| Minimum Weight Path | Minimize total weight |
The main DP state remains:
dp[mask][u]
The important part is understanding what this state represents.
Once that is clear, changing the objective from minimum to maximum or count becomes straightforward.
