Gray codes with bounded weights

Given a set HH of binary vectors of length nn, is there a cyclic listing of HH so that every two successive vectors differ in a single coordinate? The problem of the existence of such a listing, which is called a cyclic Gray code   of HH, is known to be NP-complete in general. The goal of this paper is therefore to specify boundaries between its intractability and polynomial decidability.For that purpose, we consider a restriction when the vectors of HH are of a bounded weight. A weight   of a vector u∈{0,1}nu∈{0,1}n is the number of 1’s in uu. We show that if every vertex of HH has weight kk or k+1k+1, our problem is decidable in polynomial time for k≤1k≤1 and NP-complete for k≥2k≥2. Furthermore, if k=2k=2 and for every i∈[n]i∈[n] there are at most mm vectors of HH of weight two having one in the ii-th coordinate, then the problem becomes decidable in polynomial time for m≤3m≤3 and NP-complete for m≥13m≥13.The following complementary problem is also known to be NP-hard: given an F⊆{0,1}nF⊆{0,1}n, which now plays the role of a set of faults to be avoided, is there a cyclic Gray code of {0,1}n∖F{0,1}n∖F? We show that if every vertex of FF has weight at most kk, the problem is decidable in polynomial time for k≤2k≤2 and NP-hard for k≥5k≥5. It follows that there is a function f(n)=Θ(n4) such that the existence of a cyclic Gray code of {0,1}n∖F{0,1}n∖F for a given set F⊆{0,1}nF⊆{0,1}n of size at most f(n)f(n) is NP-hard.In addition, we study the cases when the Gray code does not have to be cyclic, and moreover, when the first and the last vectors of the code are prescribed. For these two modifications, all NP-hardness and NP-completeness results hold as well.