AntInLoop

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.