Exponential Algorithms for Finding Hamiltonian Cycles and Paths¶
In this section, we will explore 4 algorithms along with their implementations. These 4 algorithms are very similar to each other, but they have subtle differences, and significant attention should be paid to these differences and the underlying idea behind each.
Hamiltonian Path¶
Algorithm 1¶
From previous sections, we realized that there is no necessary and sufficient condition for finding Hamiltonian cycles and paths. In other words, this is an NP-complete problem, and no polynomial-time algorithm exists for it. Now we will try to present an exponential algorithm for it.
Now, using dynamic programming, we define \(dp_{mask, a, b}\) as a boolean array indicating whether there exists a Hamiltonian path using vertices from the set \(mask\) that starts at vertex \(a\) and ends at vertex \(b\).
To update this function, it is sufficient to condition on the vertex before \(b\). Suppose this vertex is \(c\). It is necessary that \(c\) is a member of the set \(mask\) and also that an edge exists between \(b\) and \(c\). Finally, to determine if a Hamiltonian path exists, one can check \(dp_{2^n-1,i,j}\) for all possible \(i\) and \(j\).
So the algorithm implementation will be as follows:
#define bit(n,k) (((n)>>(k))&1)
const int maxn = 16;
bool dp[1<<maxn][maxn][maxn];
bool adj[maxn][maxn];
int main(){
// voroodi gereftan graph
int n;
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> adj[i][j];
// mohasebe dp
for(int mask = 1; mask < (1<<n); mask++){
if(__builtin_popcount(mask) == 1){
dp[mask][__builtin_ctz(mask)][__builtin_ctz(mask)] = 1;
continue;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j || bit(mask, i) == 0 || bit(mask, j) == 0)
continue;
for(int k = 0; k < n; k++){
if(k == j || bit(mask, k) == 0 || adj[k][j] == 0)
continue;
dp[mask][i][j] |= dp[mask ^ (1<<j)][i][k];
}
}
}
}
bool ans = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
ans |= dp[(1<<n)-1][i][j];
if(ans)
cout << "YES\n";
else
cout << "NO\n";
return 0;
}
As you can see, we have presented an algorithm with a time complexity of \(O(2^n * n^3)\).
Algorithm 2¶
Now we want to present a better algorithm by changing the definition of the recursive function.
Let \(dp_{mask,u}\) be a subset of vertices, say \(mask2\), such that for every member \(v\) of it, there is a Hamiltonian path from \(u\) to \(v\) using vertices in the subset \(mask\).
To update this recursive function, we must condition on the vertex we see after \(u\). Finally, to find the answer to the problem, we must check \(dp_{2^n-1,u}\) for all possible \(u\).
#define bit(n,k) (((n)>>(k))&1)
const int maxn = 16;
int dp[1<<maxn][maxn];
bool adj[maxn][maxn];
int main(){
// voroodi gereftan graph
int n;
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> adj[i][j];
// mohasebe dp
for(int mask = 1; mask < (1<<n); mask++){
if(__builtin_popcount(mask) == 1){
dp[mask][__builtin_ctz(mask)] = mask;
continue;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j || bit(mask, i) == 0 || bit(mask, j) == 0 || adj[i][j] == 0){
continue;
}
dp[mask][i] |= dp[mask ^ (1<<i)][j];
}
}
}
bool ans = 0;
for(int i = 0; i < n; i++)
if(dp[(1<<n)-1][i] != 0){
ans = 1;
if(ans)
cout << "YES\n";
else
cout << "NO\n";
return 0;
}
Thus, we were able to reduce the time complexity of the algorithm to \(O(2^n * n^2)\).
Hamiltonian Cycle¶
Algorithm 1¶
To check if a Hamiltonian cycle exists in the graph, it is sufficient to consider an arbitrary vertex, say \(a\). Then, for all neighbors of vertex \(a\), say \(b\), we determine if a Hamiltonian path exists from \(a\) to \(b\). (If it exists, first traverse the Hamiltonian path, then traverse the edge \(ab\)).
This can be done using the recursive function we used in Algorithm 1 of the previous section.
Now we will try to improve the algorithm. Since vertex \(a\) was chosen arbitrarily, we hypothesize that we can change the definition of the recursive function to achieve an algorithm with better time complexity.
We define \(dp_{mask,u}\) as a boolean array indicating whether it is possible to start from vertex \(u\), visit all vertices in the set \(mask\), and finally reach the smallest member of the set \(mask\).
The difference between this definition and the previous one is that now the endpoint of the Hamiltonian path is determined by \(mask\), and there is no need to allocate an extra dimension for it.
To update, you can condition on the vertex after \(u\).
#include<bits/stdc++.h>
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
const int maxn = 16;
bool dp[1<<maxn][maxn];
bool adj[maxn][maxn];
int main(){
// voroodi gereftan graph
int n;
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> adj[i][j];
// mohasebe dp
for(int mask = 1; mask < (1<<n); mask++){
if(__builtin_popcount(mask) == 1){
dp[mask][__builtin_ctz(mask)] = 1;
continue;
}
int low_bit = __builtin_ctz(mask);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j || bit(mask, i) == 0 || bit(mask, j) == 0 || i == low_bit || adj[i][j] == 0)
continue;
dp[mask][i] |= dp[mask ^ (1<<i)][j];
}
}
}
bool ans = 0;
for(int i = 1; i < n; i++){ // i != 0
if(dp[(1<<n)-1][i] && adj[0][i])
ans = 1;
}
if(ans)
cout << "YES\n";
else
cout << "NO\n";
return 0;
}
Thus, we arrived at an algorithm with a time complexity of \(O(2^n * n^2)\).
Algorithm 2¶
Now, drawing inspiration from Algorithm 2 of the previous section, we improve the time complexity of the solution.
We define \(dp_{mask}\) as a subset of vertices, say \(mask2\), such that from any vertex \(u\) in \(mask2\), one can start, visit all vertices in the set \(mask\), and finally reach the smallest member of \(mask\).
To update, one can condition on the starting vertex of the Hamiltonian path.
Pay attention to the code below. The array \(adj\_mask_u\) represents the set of vertices adjacent to vertex \(u\).
#define bit(n,k) (((n)>>(k))&1)
const int maxn = 16;
int dp[1<<maxn];
int adj_mask[maxn];
int main(){
// voroodi gereftan graph
int n;
cin >> n;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
bool x;
cin >> x;
if(x){
adj_mask[i] |= 1<<j;
}
}
}
// mohasebe dp
for(int mask = 1; mask < (1<<n); mask++){
if(__builtin_popcount(mask) == 1){
dp[mask] = mask;
continue;
}
int low_bit = __builtin_ctz(mask);
for(int i = 0; i < n; i++){
if(bit(mask, i) == 0 || i == low_bit)
continue;
if(dp[mask ^ (1<<i)] & adj_mask[i])
dp[mask] |= 1<<i;
}
}
bool ans = 0;
if(dp[(1<<n)-1] != 0)
ans = 1;
if(ans)
cout << "YES\n";
else
cout << "NO\n";
return 0;
}
Thus, we finally arrived at an algorithm with a time complexity of \(O(2^n * n)\).
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at اکتبر 13, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
