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.

Improve this question
$\endgroup$
3
  • 2
    $\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$
    – Michaël Cadilhac
    Commented Jul 1, 2022 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$
    – Emil Jeřábek
    Commented Jul 1, 2022 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
    Commented Jul 1, 2022 at 17:14

1 Answer 1

Reset to default
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.
Improve this answer
$\endgroup$

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