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)