# Enumerating finite set of words with Hamming distance $1$

Consider the following problem:

INPUT: a finite set $$W$$ of words over binary alphabet, all words have the same length.

OUTPUT: yes if there exists a permutation of $$W$$ such that any two consecutive words are at Hamming distance $$1$$, no otherwise.

I would like to know if this problem is NP-complete. I have a proof that if I ask for distance exactly $$4$$ instead of $$1$$ then it is NP-complete.

• This has an interpretation on subsets of $[n]$, right? Given a set of subsets of $[n]$, can we order them in such a way that there's one less/one more element between each two. Jul 1 at 15:20
• In other words, this is the Hamiltonian path problem restricted to graphs presented as induced subgraphs of the Hamming cube. Jul 1 at 16:19
• Yes, and yes. Note that if $W$ is the whole Hamming cube then the answer is always yes: this is the Gray code (en.wikipedia.org/wiki/Gray_code). I am also interested in the same problem but for distance 2 and 3, as my proof of NP-hardness works in fact for any $k\geq 4$. Jul 1 at 17:14

To prove any grid graph can be represented as a set of binary strings, consider representing a vertex of a grid graph of dimension $$n \times n$$ at position $$(x, y)$$ as a concatenation of sub-strings $$f(x) f(y)$$ where $$f(i) = 0^{i} 1^{n-i}.$$
As $$\mathrm{Hamming}(f(x_1) f(y_1), f(x_2) f(y_2)) = |x_1 - x_2| + |y_1 - y_2|$$, we have an embedding of the grid graph.
It is also possible to reduce the length of strings to $$O(\log n)$$ by modifying the function $$f(\cdot)$$ using known results of the snake-in-the-box problem.