Introduction

The standard dynamic programming method for Hamiltonian cycle is the Held-Karp style subset DP. It does not make the problem easy in the general case, but it reduces brute force from factorial time to roughly O(n^2 2^n), which is much better for small graphs.

Core Idea of the DP

Pick a start vertex, usually 0, and build paths that begin there and visit subsets of vertices exactly once. The state records two things:

• which vertices have already been visited
• which vertex the current path ends at

A common boolean state is:

dp[mask][v] = True if there is a path starting at 0, visiting exactly the vertices in mask, and ending at v.

The bitmask stores the subset. If bit i is on, vertex i is included in the partial path.

Transition Rule

From a valid state dp[mask][u], you can extend to a neighbor v when:

• 'v is not already in mask'
• there is an edge from u to v

That produces:

dp[mask | (1 << v)][v] = True

Once all vertices have been visited, you only need one final check: can the end vertex connect back to the start vertex 0? If yes, a Hamiltonian cycle exists.

Python Example

This implementation assumes an adjacency matrix where graph[u][v] is True when an edge exists:

1def has_hamiltonian_cycle(graph):
2    n = len(graph)
3    start = 0
4    full_mask = (1 << n) - 1
5
6    dp = [[False] * n for _ in range(1 << n)]
7    dp[1 << start][start] = True
8
9    for mask in range(1 << n):
10        for u in range(n):
11            if not dp[mask][u]:
12                continue
13
14            for v in range(n):
15                if mask & (1 << v):
16                    continue
17                if not graph[u][v]:
18                    continue
19
20                dp[mask | (1 << v)][v] = True
21
22    for end in range(n):
23        if end != start and dp[full_mask][end] and graph[end][start]:
24            return True
25
26    return False
27
28
29graph = [
30    [False, True,  True,  False],
31    [True,  False, True,  True ],
32    [True,  True,  False, True ],
33    [False, True,  True,  False],
34]
35
36print(has_hamiltonian_cycle(graph))

Output:

True

Why It Works

The DP avoids recomputing the same partial path question again and again. Instead of asking "is there some path over these vertices ending here?" many times recursively, it stores the answer once and reuses it.

That is the essence of the dynamic programming improvement over plain backtracking.

Recovering the Actual Cycle

If you need the cycle itself instead of a yes-or-no answer, store a parent pointer for each successful state. Then, once you find an end vertex that connects back to the start, walk the parents backward to reconstruct the full order of vertices.

This raises memory usage a bit, but the asymptotic time stays the same.

Complexity

There are 2^n possible subsets and up to n possible endpoints for each subset. For each state, transitions may inspect up to n next vertices.

That gives:

• time complexity: O(n^2 2^n)
• space complexity: O(n 2^n)

This is still exponential, so it is practical only for relatively small graphs. But compared with checking all permutations, it is a major improvement.

Common Pitfalls

• Forgetting that Hamiltonian cycle is still NP-complete even with dynamic programming.
• Mixing up Hamiltonian cycle and Hamiltonian path. The cycle must return to the start.
• Using a DP table without a fixed start vertex, which creates redundant symmetric states.
• Expecting this method to scale to very large graphs.
• Forgetting the final edge check from the last vertex back to the start.

Summary

• The classic DP algorithm is the Held-Karp subset dynamic programming method.
• States are defined by a visited-set bitmask and an ending vertex.
• Transitions extend valid partial paths to unvisited neighbors.
• After visiting all vertices, you must still verify that the path closes into a cycle.
• The algorithm runs in O(n^2 2^n) time and is practical for small graphs, not large ones.