Suppose we defined a set $S = \{x\mid0 \leq x \leq 2^n-1\}$. Notice that all element in $S$ can be represented with a $n$-bit binary string. Now consider subset $S_i$ such that,

$$S_{y_i} = \{y \in S\mid d(y,y_i) \leq t\},$$

where $y_i$ is the $i$th element of $S$ and $d(y_j,y_i)$ is the hamming distance between the binary representation of $y_j$ and $y_i$ and $t < n$. Obviously, $S_{y_i} \subset S$.

Consider the family ${\Phi = \{S_0, S_1, \ldots, S_{2^n-1}\}}$. Find ${\phi \subset \Phi}$ with smallest cardinality, so that the union of the all elements in $\phi$ is equal to original set $S$ (notice that, each element of $\phi$ is a subset of $S$).

I was not be able to solve. However, I believe it is possible to find $\phi$ with an efficient algorithm rather than using an exhaustive search.

Edit: An example-

Assume $n =3$ and $t = 1$

Then $S = \{0, 1, 2, 3, 4, 5, 6, 7\}$

So, $S_0 = \{y \in S\ |\ d(y,0) \leq 1;\} = \{0, 1, 2, 4\}$

Similarly, $S_1 = \{0, 1, 3, 5\}$; $S_2 = \{0, 2, 3, 6\}$; $S_3 = \{1, 2, 3, 7\}$; $S_4 = \{0, 4, 5, 6\}$; $S_5 = \{1, 4, 5, 7\}$; $S_6 = \{3, 4, 6, 7\}$; $S_7 = \{3, 5, 6, 7\}$;

So, $\Phi = \{S_0, S_1, S_2, S_3, S_4, S_5, S_6, S_7\}$; Now, for this case the $\phi = \{S_2, S_5\}$ as $S_2 \cup S_5 = S$

  • $\begingroup$ Can you share the context in which you encountered this task; and improve the title to make it more descriptive? $\endgroup$ – D.W. Apr 11 at 7:42
  • $\begingroup$ To be honest, this is the exact problem that I am working on. This is not a part of a big problem. $\endgroup$ – user3862410 Apr 11 at 7:56

The object you are looking for is known as a covering code. Finding the smallest covering code for a given radius is generally a difficult problem, just like its more well-known dual problem, error-correcting codes.

| cite | improve this answer | |
  • $\begingroup$ And if you are looking for known bounds: old.sztaki.hu/~keri/codes/2_tables.pdf $\endgroup$ – CodeChef Apr 11 at 8:29
  • $\begingroup$ Is there any algorithm that is used in practice? $\endgroup$ – user3862410 Apr 14 at 0:09
  • $\begingroup$ Probably. Note that you know the correct keyword, you can look it up on your own. $\endgroup$ – Yuval Filmus Apr 14 at 6:02

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.