<p>This problem is NP-complete.
The class of graphs in the question is equivalent to the <a href="https://www.graphclasses.org/classes/gc_1177.html" rel="noreferrer">cubical graphs</a> *1, but this class contains <a href="https://www.graphclasses.org/classes/gc_1057.html" rel="noreferrer">grid graphs</a>.
Because the Hamiltonian path problem in grid graphs is NP-hard [1], the original problem is NP-hard.</p>
<p>To prove any grid graph can be represented as a set of binary strings, consider representing a vertex of a grid graph of dimension <span class="math-container">$n \times n$</span> at position <span class="math-container">$(x, y)$</span> as a concatenation of sub-strings <span class="math-container">$f(x) f(y)$</span> where
<span class="math-container">$$
f(i) = 0^{i} 1^{n-i}.
$$</span></p>
<p>As <span class="math-container">$\mathrm{Hamming}(f(x_1) f(y_1), f(x_2) f(y_2)) = |x_1 - x_2| + |y_1 - y_2|$</span>, we have an embedding of the grid graph.</p>
<p>It is also possible to reduce the length of strings to <span class="math-container">$O(\log n)$</span> by modifying the function <span class="math-container">$f(\cdot)$</span> using known results of the <a href="https://en.wikipedia.org/wiki/Snake-in-the-box" rel="noreferrer">snake-in-the-box</a> problem.</p>
<p>*1: <a href="https://www.graphclasses.org/classes/gc_1159.html" rel="noreferrer">Binary Hamming</a> 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.</p>
<ul>
<li>[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. <a href="https://doi.org/10.1137/0211056" rel="noreferrer">https://doi.org/10.1137/0211056</a>.</li>
</ul>

CC BY-SA 4.0
2022-07-02T03:32:13.557Z
2022-07-02T03:32:13.557Z
pcpthm
<p>Consider the following problem:</p>
<p><strong>INPUT</strong>: a finite set <span class="math-container">$W$</span> of words over binary alphabet, all words have the same length.</p>
<p><strong>OUTPUT</strong>: yes if there exists a permutation of <span class="math-container">$W$</span> such that any two consecutive words are at Hamming distance <span class="math-container">$1$</span>, no otherwise.</p>
<p>I would like to know if this problem is NP-complete.
I have a proof that if I ask for distance exactly <span class="math-container">$4$</span> instead of <span class="math-container">$1$</span> then it is NP-complete.</p>

CC BY-SA 4.0
2022-07-01T15:20:57.460Z
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.
Michaël Cadilhac
CC BY-SA 4.0
2022-07-01T16:19:00.493Z
In other words, this is the Hamiltonian path problem restricted to graphs presented as induced subgraphs of the Hamming cube.
Emil Jeřábek
CC BY-SA 4.0
2022-07-01T17:14:47.743Z
Yes, and yes. Note that if $W$ is the whole Hamming cube then the answer is always yes: this is the Gray code (https://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$.
M.Monet
<np>
Enumerating finite set of words with Hamming distance $1$
M.Monet
# Enumerating finite set of words with Hamming distance $1$

(Asked by: username_0 on 2022-07-01)

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.

**Tags:** np
> **Comments:**
> **username_1**: 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.  
> **username_2**: In other words, this is the Hamiltonian path problem restricted to graphs presented as induced subgraphs of the Hamming cube.  
> **username_0**: Yes, and yes. Note that if $W$ is the whole Hamming cube then the answer is always yes: this is the Gray code (https://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$.  

---

## 1 answers

### Answer by username_3 on 2022-07-02. Score: 9 | Accepted answer

This problem is NP-complete.
The class of graphs in the question is equivalent to the [cubical graphs](https://www.graphclasses.org/classes/gc_1177.html) \*1, but this class contains [grid graphs](https://www.graphclasses.org/classes/gc_1057.html).
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](https://en.wikipedia.org/wiki/Snake-in-the-box) problem.

\*1: [Binary Hamming](https://www.graphclasses.org/classes/gc_1159.html) 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>.


---

