41.02Intermediate / Advanced5 topics20 min3 interactive animations

Hamiltonian problems

A Hamiltonian cycle visits every vertex exactly once. Unlike Euler trails, no fast algorithm is known: the problem is NP-complete. Backtracking and bitmask dynamic programming solve small instances, and the travelling salesman problem is its weighted form.

Learning goals

Define Hamiltonian paths and cycles and verify a candidate in O(n)
Explain NP-completeness with the path-to-cycle reduction
Write backtracking and bitmask-DP solvers
Connect Hamiltonian cycles to the travelling salesman problem

Prerequisites

Backtracking (Chapter 24)Bitmask operations (Chapter 14)Euler trails (Lesson 41.01)

Visit every city once and return home: a tour of all stops, a drilling route on a circuit board, a delivery round. Euler's problem about edges is easy, but this problem about vertices is the classic example of one that is easy to check and, as far as anyone knows, hard to solve.

41.02.1

Hamiltonian path/cycle

A **Hamiltonian path** visits every vertex exactly once; a **Hamiltonian cycle** is a Hamiltonian path whose last vertex is adjacent to its first. Some graphs have neither, some have a path but no cycle (a simple path graph), and complete graphs have both.

Given a candidate ordering of the vertices, checking it takes only O(n): confirm it is a permutation and that consecutive vertices are adjacent (and, for a cycle, that the last is adjacent to the first). This asymmetry between fast **checking** and slow **finding** is exactly what the class NP describes.

Necessary conditions can rule out some graphs quickly. A vertex of degree 1 cannot lie on a Hamiltonian cycle, and removing k vertices from a graph with a Hamiltonian cycle leaves at most k connected pieces. None of these is sufficient. Dirac's theorem gives a sufficient condition: a simple graph with n ≥ 3 vertices in which every vertex has degree at least n / 2 has a Hamiltonian cycle.

Property	Euler trail	Hamiltonian path
Visits	every edge once	every vertex once
Test	degrees + connectivity, O(V + E)	no polynomial algorithm known
Certificate check	O(E)	O(V)
Complexity class	P	NP-complete

Java

1// order = the vertices of a claimed Hamiltonian path (cycle = false) or cycle (cycle = true): a certificate checkable in O(n)
2static boolean verifyHamiltonian(boolean[][] adj, int[] order, boolean cycle) {
3    int n = adj.length;
4    if (order.length != n) return false;
5    boolean[] seen = new boolean[n];
6    for (int v : order) {
7        if (seen[v]) return false;                                    // a vertex repeats
8        seen[v] = true;
9    }
10    for (int i = 0; i + 1 < n; i++) if (!adj[order[i]][order[i + 1]]) return false;
11    return !cycle || adj[order[n - 1]][order[0]];
12}

41.02.2

NP-completeness

The Hamiltonian cycle problem is **NP-complete**: it is in NP (a certificate is checked in O(n)), and every problem in NP reduces to it in polynomial time. The proof by reduction from 3-SAT builds a graph out of gadgets; the fact itself is what matters here: unless P = NP, no algorithm solves every instance in polynomial time.

The Hamiltonian **path** problem is equivalent. Add one new vertex joined to every old vertex. A Hamiltonian cycle in the new graph must enter and leave the new vertex through two old vertices and visit all the other vertices in between, which is exactly a Hamiltonian path of the old graph. Conversely, a path with ends a and b closes into a cycle through the new vertex. So a solver for one problem solves the other with one extra vertex.

The same machinery shows that the travelling salesman problem is NP-hard: set the cost of every existing edge to 1 and every missing edge to 2 in the complete graph; a tour of cost n exists exactly when the graph has a Hamiltonian cycle. This is why practical TSP software uses heuristics and branch and bound, and why exact methods such as the DP in this lesson stop at about 20 vertices.

Problem	Status	Typical exact limit
Hamiltonian cycle / path	NP-complete	n ≈ 20 with bitmask DP, more with pruning
Travelling salesman (optimisation)	NP-hard	n ≈ 20-25 with DP; thousands with branch and cut
Euler circuit	P	millions of edges
Shortest path	P	millions of edges

Java

1// a Hamiltonian PATH exists in G exactly when G plus a new vertex joined to every vertex has a Hamiltonian CYCLE
2static boolean[][] addUniversalVertex(boolean[][] adj) {
3    int n = adj.length;
4    boolean[][] bigger = new boolean[n + 1][n + 1];
5    for (int u = 0; u < n; u++) System.arraycopy(adj[u], 0, bigger[u], 0, n);
6    for (int u = 0; u < n; u++) bigger[u][n] = bigger[n][u] = true;
7    return bigger;
8}

41.02.3

Backtracking

The simplest exact method is **backtracking**: fix vertex 0 as the start (a cycle can be rotated), then extend the path one vertex at a time with an unused neighbour of the last vertex, and undo the step when it leads nowhere. When all n vertices are on the path, a final check closes the cycle.

The worst case is (n − 1)! orderings, but dead ends are pruned the moment a vertex has no unused neighbour, so graphs with structure are fast. Open the animation. The default graph succeeds after 4 extensions and no backtracking: the path 0→1→2→3→4 closes by the edge 4-0. The “No cycle” preset has a pendant vertex 4 whose only neighbour is 0; the search extends and backtracks 7 times each before it can conclude that no ordering works.

Cheap pruning makes real solvers much better: a vertex with fewer than two unused neighbours kills the branch, connectivity of the unused part can be checked, and trying the most constrained vertex first reduces the branching.

Java

1static boolean extend(int pos, int[] path, boolean[] used, boolean[][] adj) {
2    int n = path.length, last = path[pos - 1];
3    if (pos == n) return adj[last][path[0]];                          // every vertex is on the path: close the cycle
4    for (int v = 1; v < n; v++) {
5        if (used[v] || !adj[last][v]) continue;
6        used[v] = true;
7        path[pos] = v;
8        if (extend(pos + 1, path, used, adj)) return true;
9        used[v] = false;                                              // undo and try the next vertex
10    }
11    return false;
12}
13static boolean hamiltonianCycle(boolean[][] adj) {                    // vertex 0 is fixed as the start of the cycle
14    int n = adj.length;
15    int[] path = new int[n];
16    boolean[] used = new boolean[n];
17    used[0] = true;
18    return extend(1, path, used, adj);
19}

Worst

O(n!)

Space

O(n)

Hamiltonian cycles: backtracking, bitmask DP and the travelling salesman problem

Interactive · edit the input

undirected graph · 5 vertices · 7 edges

Edge being triedEdge on the cycle / state reachedClosing edge

path so far

0start

Setup

A Hamiltonian cycle visits every vertex exactly once and returns to the start. Fix vertex 0 as the start (a cycle can be rotated) and try to extend the path one vertex at a time, undoing the last step when stuck.

Step 1 / 7

Java

1static boolean extend(int pos, int[] path, boolean[] used, boolean[][] adj) {
2    int n = path.length, last = path[pos - 1];
3    if (pos == n) return adj[last][path[0]];                          // every vertex is on the path: close the cycle
4    for (int v = 1; v < n; v++) {
5        if (used[v] || !adj[last][v]) continue;
6        used[v] = true;
7        path[pos] = v;
8        if (extend(pos + 1, path, used, adj)) return true;
9        used[v] = false;                                              // undo and try the next vertex
10    }
11    return false;
12}
13static boolean hamiltonianCycle(boolean[][] adj) {                    // vertex 0 is fixed as the start of the cycle
14    int n = adj.length;
15    int[] path = new int[n];
16    boolean[] used = new boolean[n];
17    used[0] = true;
18    return extend(1, path, used, adj);
19}
20static boolean hamiltonianCycleDp(boolean[][] adj) {                  // dp[mask][v]: a path from 0 visits exactly mask and ends at v
21    int n = adj.length, full = (1 << n) - 1;
22    boolean[][] dp = new boolean[1 << n][n];
23    dp[1][0] = true;
24    for (int mask = 1; mask <= full; mask++)
25        for (int v = 0; v < n; v++) {
26            if (!dp[mask][v]) continue;
27            for (int w = 1; w < n; w++)
28                if ((mask >> w & 1) == 0 && adj[v][w]) dp[mask | 1 << w][w] = true;
29        }
30    for (int v = 1; v < n; v++) if (dp[full][v] && adj[v][0]) return true;
31    return false;
32}
33static int tsp(int[][] w) {                                           // w[a][b] = 0 means no edge; returns the cheapest tour or -1
34    int n = w.length, full = (1 << n) - 1, inf = Integer.MAX_VALUE / 2;
35    int[][] dp = new int[1 << n][n];
36    for (int[] r : dp) Arrays.fill(r, inf);
37    dp[1][0] = 0;
38    for (int mask = 1; mask <= full; mask++)
39        for (int v = 0; v < n; v++) {
40            if (dp[mask][v] >= inf) continue;
41            for (int x = 1; x < n; x++)
42                if ((mask >> x & 1) == 0 && w[v][x] > 0)
43                    dp[mask | 1 << x][x] = Math.min(dp[mask | 1 << x][x], dp[mask][v] + w[v][x]);
44        }
45    int best = inf;
46    for (int v = 1; v < n; v++) if (dp[full][v] < inf && w[v][0] > 0) best = Math.min(best, dp[full][v] + w[v][0]);
47    return best >= inf ? -1 : best;
48}

Live state

0 extensions0 backtracks

edges

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L13	n=5 edges=7	A Hamiltonian cycle visits every vertex exactly once and returns to the start. Fix vertex 0 as the start (a cycle can be rotated) and try to extend the path one vertex at a time, undoing the last step when stuck.
2	L7	pos=1 vertex=1 path=0→1	Extend the path with 1 (edge 0-1).
3	L7	pos=2 vertex=2 path=0→1→2	Extend the path with 2 (edge 1-2).
4	L7	pos=3 vertex=3 path=0→1→2→3	Extend the path with 3 (edge 2-3).
5	L7	pos=4 vertex=4 path=0→1→2→3→4	Extend the path with 4 (edge 3-4).
6	L3	path=0→1→2→3→4 closes=yes	All 5 vertices are on the path and 4-0 closes the cycle.
7	L18	return=0→1→2→3→4→0 extensions=4	Hamiltonian cycle 0→1→2→3→4→0, found after 4 extensions and 0 backtracks.

41.02.4

Bitmask DP

Backtracking recomputes the same situations again and again: what matters for the future of a path is only **which vertices were used** and **where it currently ends**, not the order in which they were visited. That gives the **Held-Karp** style table dp[mask][v]: true when some path starting at vertex 0 visits exactly the vertices in mask and ends at v.

Start with dp[{0}][0] = true. For every reachable state and every unvisited neighbour w of v, mark dp[mask ∪ {w}][w]. A Hamiltonian cycle exists exactly when some dp[all][v] is true with v adjacent to 0. The table has 2^n · n entries and each takes O(n) to expand, so the time is O(2^n · n^2) against O(n!), which makes n = 20 feasible.

In the animation, choose the second method on the same graph: the 18 reachable states are printed mask by mask, with the possible last vertices of each. The graph has several cycles; the final message shows one of them, reconstructed from the table (the Java method only returns the boolean, reconstruction needs a parent table).

Java

1static boolean hamiltonianCycleDp(boolean[][] adj) {                  // dp[mask][v]: a path from 0 visits exactly mask and ends at v
2    int n = adj.length, full = (1 << n) - 1;
3    boolean[][] dp = new boolean[1 << n][n];
4    dp[1][0] = true;
5    for (int mask = 1; mask <= full; mask++)
6        for (int v = 0; v < n; v++) {
7            if (!dp[mask][v]) continue;
8            for (int w = 1; w < n; w++)
9                if ((mask >> w & 1) == 0 && adj[v][w]) dp[mask | 1 << w][w] = true;
10        }
11    for (int v = 1; v < n; v++) if (dp[full][v] && adj[v][0]) return true;
12    return false;
13}

Worst

O(2^n · n²)

Space

O(2^n · n)

Hamiltonian cycles: backtracking, bitmask DP and the travelling salesman problem

Interactive · edit the input

undirected graph · 5 vertices · 7 edges

Edge being triedEdge on the cycle / state reachedClosing edge

path so far

0start

Setup

Step 1 / 7

Java

1static boolean extend(int pos, int[] path, boolean[] used, boolean[][] adj) {
2    int n = path.length, last = path[pos - 1];
3    if (pos == n) return adj[last][path[0]];                          // every vertex is on the path: close the cycle
4    for (int v = 1; v < n; v++) {
5        if (used[v] || !adj[last][v]) continue;
6        used[v] = true;
7        path[pos] = v;
8        if (extend(pos + 1, path, used, adj)) return true;
9        used[v] = false;                                              // undo and try the next vertex
10    }
11    return false;
12}
13static boolean hamiltonianCycle(boolean[][] adj) {                    // vertex 0 is fixed as the start of the cycle
14    int n = adj.length;
15    int[] path = new int[n];
16    boolean[] used = new boolean[n];
17    used[0] = true;
18    return extend(1, path, used, adj);
19}
20static boolean hamiltonianCycleDp(boolean[][] adj) {                  // dp[mask][v]: a path from 0 visits exactly mask and ends at v
21    int n = adj.length, full = (1 << n) - 1;
22    boolean[][] dp = new boolean[1 << n][n];
23    dp[1][0] = true;
24    for (int mask = 1; mask <= full; mask++)
25        for (int v = 0; v < n; v++) {
26            if (!dp[mask][v]) continue;
27            for (int w = 1; w < n; w++)
28                if ((mask >> w & 1) == 0 && adj[v][w]) dp[mask | 1 << w][w] = true;
29        }
30    for (int v = 1; v < n; v++) if (dp[full][v] && adj[v][0]) return true;
31    return false;
32}
33static int tsp(int[][] w) {                                           // w[a][b] = 0 means no edge; returns the cheapest tour or -1
34    int n = w.length, full = (1 << n) - 1, inf = Integer.MAX_VALUE / 2;
35    int[][] dp = new int[1 << n][n];
36    for (int[] r : dp) Arrays.fill(r, inf);
37    dp[1][0] = 0;
38    for (int mask = 1; mask <= full; mask++)
39        for (int v = 0; v < n; v++) {
40            if (dp[mask][v] >= inf) continue;
41            for (int x = 1; x < n; x++)
42                if ((mask >> x & 1) == 0 && w[v][x] > 0)
43                    dp[mask | 1 << x][x] = Math.min(dp[mask | 1 << x][x], dp[mask][v] + w[v][x]);
44        }
45    int best = inf;
46    for (int v = 1; v < n; v++) if (dp[full][v] < inf && w[v][0] > 0) best = Math.min(best, dp[full][v] + w[v][0]);
47    return best >= inf ? -1 : best;
48}

Live state

0 extensions0 backtracks

edges

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L13	n=5 edges=7	A Hamiltonian cycle visits every vertex exactly once and returns to the start. Fix vertex 0 as the start (a cycle can be rotated) and try to extend the path one vertex at a time, undoing the last step when stuck.
2	L7	pos=1 vertex=1 path=0→1	Extend the path with 1 (edge 0-1).
3	L7	pos=2 vertex=2 path=0→1→2	Extend the path with 2 (edge 1-2).
4	L7	pos=3 vertex=3 path=0→1→2→3	Extend the path with 3 (edge 2-3).
5	L7	pos=4 vertex=4 path=0→1→2→3→4	Extend the path with 4 (edge 3-4).
6	L3	path=0→1→2→3→4 closes=yes	All 5 vertices are on the path and 4-0 closes the cycle.
7	L18	return=0→1→2→3→4→0 extensions=4	Hamiltonian cycle 0→1→2→3→4→0, found after 4 extensions and 0 backtracks.

41.02.5

TSP connection

The **travelling salesman problem (TSP)** asks for the cheapest Hamiltonian cycle in a weighted graph. The Held-Karp table from the previous section turns into a minimisation: dp[mask][v] is now the **cheapest cost** of a path from 0 through exactly mask ending at v, and each extension adds the edge weight. The best tour is the minimum over v of dp[all][v] + w[v][0].

Missing edges are expressed by weight 0 in the code (all real weights are positive), so the same routine also answers “is there any tour?” by returning -1. In the animation, choose the third method. The weighted preset has a cheapest tour of cost 16, 0→4→3→2→1→0, and the complete graph on 4 vertices costs 6 with the tour 0→3→2→1→0.

The DP is exact but exponential in memory as well: 2^n · n integers. For larger instances use heuristics (nearest neighbour, 2-opt, Christofides' 1.5-approximation for metric TSP) or integer-programming solvers. A common contest pattern is exactly this DP with n ≤ 16 to 20.

Java

1static int tsp(int[][] w) {                                           // w[a][b] = 0 means no edge; returns the cheapest tour or -1
2    int n = w.length, full = (1 << n) - 1, inf = Integer.MAX_VALUE / 2;
3    int[][] dp = new int[1 << n][n];
4    for (int[] r : dp) Arrays.fill(r, inf);
5    dp[1][0] = 0;
6    for (int mask = 1; mask <= full; mask++)
7        for (int v = 0; v < n; v++) {
8            if (dp[mask][v] >= inf) continue;
9            for (int x = 1; x < n; x++)
10                if ((mask >> x & 1) == 0 && w[v][x] > 0)
11                    dp[mask | 1 << x][x] = Math.min(dp[mask | 1 << x][x], dp[mask][v] + w[v][x]);
12        }
13    int best = inf;
14    for (int v = 1; v < n; v++) if (dp[full][v] < inf && w[v][0] > 0) best = Math.min(best, dp[full][v] + w[v][0]);
15    return best >= inf ? -1 : best;
16}

Worst

O(2^n · n²)

Space

O(2^n · n)

Hamiltonian cycles: backtracking, bitmask DP and the travelling salesman problem

Interactive · edit the input

undirected graph · 5 vertices · 7 edges

Edge being triedEdge on the cycle / state reachedClosing edge

path so far

0start

Setup

Step 1 / 7

Java

1static boolean extend(int pos, int[] path, boolean[] used, boolean[][] adj) {
2    int n = path.length, last = path[pos - 1];
3    if (pos == n) return adj[last][path[0]];                          // every vertex is on the path: close the cycle
4    for (int v = 1; v < n; v++) {
5        if (used[v] || !adj[last][v]) continue;
6        used[v] = true;
7        path[pos] = v;
8        if (extend(pos + 1, path, used, adj)) return true;
9        used[v] = false;                                              // undo and try the next vertex
10    }
11    return false;
12}
13static boolean hamiltonianCycle(boolean[][] adj) {                    // vertex 0 is fixed as the start of the cycle
14    int n = adj.length;
15    int[] path = new int[n];
16    boolean[] used = new boolean[n];
17    used[0] = true;
18    return extend(1, path, used, adj);
19}
20static boolean hamiltonianCycleDp(boolean[][] adj) {                  // dp[mask][v]: a path from 0 visits exactly mask and ends at v
21    int n = adj.length, full = (1 << n) - 1;
22    boolean[][] dp = new boolean[1 << n][n];
23    dp[1][0] = true;
24    for (int mask = 1; mask <= full; mask++)
25        for (int v = 0; v < n; v++) {
26            if (!dp[mask][v]) continue;
27            for (int w = 1; w < n; w++)
28                if ((mask >> w & 1) == 0 && adj[v][w]) dp[mask | 1 << w][w] = true;
29        }
30    for (int v = 1; v < n; v++) if (dp[full][v] && adj[v][0]) return true;
31    return false;
32}
33static int tsp(int[][] w) {                                           // w[a][b] = 0 means no edge; returns the cheapest tour or -1
34    int n = w.length, full = (1 << n) - 1, inf = Integer.MAX_VALUE / 2;
35    int[][] dp = new int[1 << n][n];
36    for (int[] r : dp) Arrays.fill(r, inf);
37    dp[1][0] = 0;
38    for (int mask = 1; mask <= full; mask++)
39        for (int v = 0; v < n; v++) {
40            if (dp[mask][v] >= inf) continue;
41            for (int x = 1; x < n; x++)
42                if ((mask >> x & 1) == 0 && w[v][x] > 0)
43                    dp[mask | 1 << x][x] = Math.min(dp[mask | 1 << x][x], dp[mask][v] + w[v][x]);
44        }
45    int best = inf;
46    for (int v = 1; v < n; v++) if (dp[full][v] < inf && w[v][0] > 0) best = Math.min(best, dp[full][v] + w[v][0]);
47    return best >= inf ? -1 : best;
48}

Live state

0 extensions0 backtracks

edges

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L13	n=5 edges=7	A Hamiltonian cycle visits every vertex exactly once and returns to the start. Fix vertex 0 as the start (a cycle can be rotated) and try to extend the path one vertex at a time, undoing the last step when stuck.
2	L7	pos=1 vertex=1 path=0→1	Extend the path with 1 (edge 0-1).
3	L7	pos=2 vertex=2 path=0→1→2	Extend the path with 2 (edge 1-2).
4	L7	pos=3 vertex=3 path=0→1→2→3	Extend the path with 3 (edge 2-3).
5	L7	pos=4 vertex=4 path=0→1→2→3→4	Extend the path with 4 (edge 3-4).
6	L3	path=0→1→2→3→4 closes=yes	All 5 vertices are on the path and 4-0 closes the cycle.
7	L18	return=0→1→2→3→4→0 extensions=4	Hamiltonian cycle 0→1→2→3→4→0, found after 4 extensions and 0 backtracks.

Practice ladder

Now try it yourself

Easy

Path with Maximum Gold

Medium

Unique Paths III
Shortest Path Visiting All Nodes

Advanced

Find the Shortest Superstring
Minimum Number of Work Sessions to Finish the Tasks

Key takeaways

Hamiltonian cycle: easy to check, no known polynomial algorithm (NP-complete).
Backtracking is O(n!) but prunes well; bitmask DP is O(2^n · n²).
TSP is the weighted Hamiltonian cycle; Held-Karp DP solves it exactly up to about n = 20.