Skip to main content

Bitmask DP: TSP and Subset-Enumeration DP

What This Concept Is​

A bitmask exactly represents a subset of n indexed objects. It is an encoding, not a reduction in the number of possible subsets. Held-Karp TSP stores a minimum path cost for (mask,last) starting at city 0, visiting exactly mask, and ending at last. This keeps the history information that endpoint-only DP loses.

For n>=2, initialize only D({0},0)=0; every other state is unreachable. Extend to an unvisited city v when edge last->v exists. At the full mask, add the edge back to 0 and minimize. The lab permits signed integer edge costs and missing edges (None), with no repeated city except the closing 0.

Why It Matters Here​

This is a correct DP for an exponentially large state family. It teaches why "DP" and "polynomial" are not synonyms and why a fixed universal cutoff such as n=20 is misleading. Container overhead, reachable density, transitions, witness storage and available memory all affect feasibility.

Concrete Examples​

For the directed matrix:

0   2   9  10
1   0   6   4
15  7   0   8
6   3  12   0

The six rooted tours have costs 22,33,26,21,34,30 in permutation order 123,132,213,231,312,321. The optimum is 21 along 0,2,3,1,0. An open path is not a tour: forgetting the return edge changes the objective. Store predecessor endpoints with the previous mask; clearing the final city's bit decreases the mask size during reconstruction.

An incomplete directed graph may have no Hamiltonian tour. Return an explicit impossible status, not 0 or a fabricated infinity-cost witness. Negative edges do not imply an unbounded objective here: the contract allows only finitely many visits. This differs from unrestricted shortest-walk negative-cycle behavior.

Cost. O(n2^n) possible state slots and up to n transitions per state give O(n²2^n) arithmetic work and O(n*2^n) storage. For n=20, a rectangular n*2^n array has 20,971,520 slots; at eight bytes each that alone is 160 MiB. Python dictionaries, integer objects and parents add substantial overhead. Store only reachable states if useful, but retain a worst-case bound.

Submask enumeration. Other subset DPs partition a mask into two pieces. Iterating every submask for every mask costs Θ(3^n), not Θ(2^n). Nonempty submask iteration uses sub=(sub-1)&mask; handle zero explicitly and stop before wrapping it back to the full mask.

Common Confusion / Misconceptions​

Allowing every singleton as a zero-cost start solves a different start condition. Repeated cities are forbidden even if a negative edge makes revisiting attractive. Increasing numeric masks respects transitions that add a new bit, but arbitrary mask transforms need their own order. A fixed-width language must also ensure the bit shifts and storage indices are representable.

How To Use It​

Write the exact subset meaning and distinguished start. Prove path extension preserves visit uniqueness, then show every legal rooted tour is represented. Estimate slots and transitions before allocation. Compare tiny instances against all rooted permutations; independently check the returned tour's vertices, edges, closing edge and recomputed total. Accept tied optimal tours.

Check Yourself​

What does last retain that mask alone loses? Why are negative edges allowed without a negative-cycle pass? Why is the closing edge necessary?

Mini Drill or Application​

Two cities have cost 5 from 0 to 1 and no edge back. Feedback: a path exists, but no tour. Add return cost -2 and the tour costs 3. For a single city, this lab defines cost 0 and route [0,0] without using a diagonal edge.

Read This Only If Stuck​

Skiena: limitations of DP and subset history. Check equations against the PDF when OCR damages subset notation; use this module's explicit start and closing conventions.