How to Check for existence of Hamiltonian walk in O(2^n) of memory and O(2^n *n) of time

Question

We can simply modify the travelling salesman problem to get whether a Hamilton walk exists or not in O(2^N * N^2)Time Complexity.

But I read it at codeforces that it is possible to solve this problem in O(2^N * N) Time .

Although , I cannot understand the state they are considering, but they are kind of compressing the original state of Travelling Salesman Problem.

Can someone give me a detailed explanation, I am new to bitmasking + DP (Infact I started today :D)

If you want you can look Point 4 at Codeforces

Answer 1

Terminology:

1. binary (x) means x is based 2.
2. Nodes numbered starting from 0
3. mask always represent a set of nodes. A node i is in mask means 2^i AND mask != 0. In the same way set mask-i (here - means removing i from the set) can be represented as mask XOR 2^i in bitmask.

Let mask be the bitmask of a set of nodes. We define dp[mask] as the bitmask of another set of nodes, which contains a node i if and only if:

1. i in mask
2. a hamilton walk exists for the set of nodes mask, which ends in node i

For example, dp[binary(1011)] = binary(1010) means that a hamilton walk exists for binary(1011) which ends in node 1, and another hamilton walk exists for binary(1011) which ends in node 3

So for N nodes, a hamilton walk exists for all of them if dp[2^N - 1] != 0

Then as described in the Codeforces link you posted, we can calculate dp[] by:

When mask only contains one node i

dp[2^i] = 2^i (which means for a single node, a walk always exists, and it ends at itself.

Otherwise

Given mask, by definition of dp[mask], for every node i in mask, we want to know if a walk exist for mask, and ends at i. To calculate this, we first check if any walk exists for the set of nodes mask-i, then check among those walks of mask-i, if there's a walk ends at a node j that's connected to i. Since combining them gives us a walk of mask that ends at i.

To make this step faster, we pre-process M[i] to be the bitmask of all notes connected to i. So i in dp[mask] if dp[mask XOR 2^i] AND M[i] != 0.

To explain a bit more about this step, dp[mask XOR 2^i] is the set of nodes that walk of mask-i can end, and M[i] is the set of nodes that's directly connected to i. So the AND of them means if any walk of mask that ends in i exists.

dp[] is O(2^N) in space. Calculating dp[] looks like

for mask = range(0, 2^N):
  for i in range(0,N):
    if 2^i AND mask != 0: # Node i in mask
      if (mask only has one node) || (dp[mask XOR 2^i] AND M[i] != 0):
        dp[mask] = dp[mask] OR 2^i # adding node i to dp[mask]

Which is O(2^N * N)

Answer 2

[EDIT: After seeing the other answer, I realise I answered the wrong question. Maybe this info is still useful? If not, I'll delete this. Let me know in a comment.]

They give a clear statement of what each entry of the DP table will hold. It's the solution to a particular subproblem consisting of just a particular subset of vertices, with the additional constraint that the path must end at a particular vertex:

Let dp[mask][i] be the length of the shortest Hamiltonian walk in the subgraph generated by vertices in mask, that ends in the vertex i.

Every path ends at some vertex, so the solution to the original problem (or at least its length) can be found by looking for the minimum of dp[(1 << n) - 1][i] over all 0 <= i < n ((1 << n) - 1 is just a nice trick for creating a bitset with the bottommost n bits all set to 1).

The main update rule (which I've slightly paraphrased below due to formatting limitations) could maybe benefit from more explanation:

dp[mask][i] = min(dp[mask XOR (1 << i)][j] + d(j, i)) over all j such that bit(j, mask) = 1 and (j, i) is an edge

So to populate dp[mask][i] we want to solve the subproblem for the set of vertices in mask, under the constraint that the last vertex in the path is i. First, notice that any path P that goes through all the vertices in mask and ends at i must have a final edge (assuming that there are at least 2 vertices in mask). This edge will be from some non-i vertex j in mask, to i. For convenience, let k be the number of vertices in mask that have an out-edge to i. Let Q be the same path as P, but with its final edge (j, i) discarded: then the length of P is length(Q) + d(j, i). Since any path can be decomposed this way, we could break up the set of all paths through mask to i into k groups according to their final edge, find the best path in each group, and then pick the best of these k minima, and this will guarantee that we haven't overlooked any possibilities.

More formally, to find the shortest path P it would suffice to consider all k possible final edges (j, i), for each such choice finding a path Q through the remaining vertices in mask (i.e., all vertices except for i itself) that ends at j and minimises length(Q) + d(j, i), and then picking the minimum of these minima.

At first, grouping by final edge doesn't seem to help much. But notice that for a particular choice of j, any path Q that ends at j and minimises length(Q) + d(j, i) also minimises length(Q) and vice versa, since d(j, i) is just a fixed extra cost when j (and of course i) are fixed. And it so happens that we already know such a path (or at least its length, which is all we actually need): it is dp[mask XOR (1 << i)][j]! (1 << i) means "the binary integer 1 shifted left i times" -- this creates a bitset consisting of a single vertex, namely i; the XOR has the effect of removing this vertex from mask (since we already know the corresponding bit must be 1 in mask). All in all, mask XOR (1 << i) means mask \ {i} in more mathematical notation.

We still don't know which penultimate vertex j is the best, so we have to try all k of them and pick the best as before -- but finding the best path Q for each choice of j is now a simple O(1) array lookup instead of an exponential-time search :)