9
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 1 at 15:20
  • 2
    $\begingroup$ In other words, this is the Hamiltonian path problem restricted to graphs presented as induced subgraphs of the Hamming cube. $\endgroup$ Jul 1 at 16:19
  • 1
    $\begingroup$ 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$. $\endgroup$
    – M.Monet
    Jul 1 at 17:14

1 Answer 1

9
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.