# 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

This problem is NP-complete. The class of graphs in the question is equivalent to the cubical graphs *1, but this class contains grid graphs. Because the Hamiltonian path problem in grid graphs is NP-hard [1], the original problem is NP-hard.

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.

*1: Binary Hamming on the ISGCI is a different class. This class requires the Hamming distance to match the distance in the graph for any pair of vertices, not necessarily adjacent.

• [1] Itai, Alon, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter. “Hamilton Paths in Grid Graphs.” SIAM Journal on Computing 11, no. 4 (November 1982): 676–86. https://doi.org/10.1137/0211056.