Give the Held-Karp dynamic program for the travelling salesman problem, state its exact time and space complexity, and compute both for 20 cities. Why does the state have to include the subset rather than only the count of visited cities?

Give the Held-Karp dynamic program for the travelling salesman problem, state its exact time and space complexity, and compute both for 20 cities. Why does the state have to include the subset rather than only the count of visited cities?

Approach: Index the table by the set of visited cities and the current city, then count states and transitions to get the bound and substitute the numbers.

O(n^2 * 2^n) time and O(n * 2^n) space, which for n = 20 is about 4.2 * 10^8 operations and 2.1 * 10^7 table entries. The bitmask dynamic programming table defines dp[S][j] as the cost of the cheapest path that starts at city 1, visits exactly the set S and ends at j, with the transition dp[S | {k}][k] = min over j in S of dp[S][j] + d(j,k). There are 2^n subsets times n end cities, which is the n * 2^n state count, and each state scans n transitions, giving the n^2 * 2^n time. The subset is required in the state because the remaining cost depends on which cities are still unvisited, so two partial tours of the same length that have visited different sets cannot be merged. Keeping only the count would let the recursion revisit a city and would not be a valid tour. The result is exponential but far below the 19! of brute force enumeration, and the space is the binding constraint in practice, since 20 cities need roughly 168 megabytes at 8 bytes an entry while 25 cities need about 6.7 gigabytes.

Follow-up: How does the same bitmask idea solve minimum cost assignment, and why is that problem actually polynomial?

Key concepts: bitmask dynamic programming, subset state, state count, exponential space.