1
$\begingroup$

Consider the Closest String problem:

Input: Strings $s_1, \dots, s_m \in \Sigma^n$ and $k \in \mathbb{N}$.

Question: Is there $s \in \Sigma^n$ for which $d_H(s, s_i) \leq k$ for all $i \in [1..m]$?

We denote with $d_H$ the Hamming distance, a string metric.

Since this is an NP-hard problem, no efficient algorithm is known. One non-trivial approach is this:

  1. Choose $s \leftarrow s_{i_0} \in \{s_1, \dots, s_m\}$ arbitrary.
    Let $d \leftarrow k$.
  2. If $s$ is a (feasible) solution, stop and answer "yes".
    If $d < 0$ or $d_H(s, s_i) > k + d$ for some $i \in [1..m]$, stop and answer "no".
  3. Else, pick any $s_j$ with $d_H(s,s_j) > k$.
  4. Pick indices $P \subseteq \{ i \mid s[i] \neq s_j[i] \}$ with $|P| = k+1$.
  5. Recurse (i.e. branch and go to step 2) on $s \leftarrow s[1] \cdots s[i-1] \cdot s_j[i] \cdot s[i+1] \cdots s[n]$ and $d \leftarrow d-1$ for every $i \in P$; answer with the logical disjunction over the answers.

One can show that this (abstract) algorithm solves Closest String in time $O(mn + nk \cdot k^k)$ (in the uniform RAM model).

Now, if $k$ is chosen minimally, the algorithm clearly constructs an optimal solution along the way. The question then is: considering the non-determinism in steps 1, 3 and 4, can the algorithm find every optimal solution?

Note how the algorithm stops whenever it encounters a feasible solution, so some solutions are "hidden" behind feasible ones -- of course, we do not explore the whole search space. For instance, on $(\{000,111\}, 2)$ the algorithm finds some optimal solutions only starting in $000$, others only from $111$ -- but all can be found.

Are there instances for which some optimal solutions hide "in the middle"? Formally,

$\qquad\displaystyle \exists w \in \mathrm{Opt}\ \forall s_i\ \exists w' \in \mathrm{Opt}.\ d_H(w', s_i) < d_H(w, s_i)\quad$?

I have tried proving the opposite without success. In particular, we know that every optimal solution has to have distance exactly $k$ to at least one input string; combining several such pairs using the triangle inequality led me nowhere.
Needless to say, I have not been able to come up with an example of "hidden" optimal solutions, either.

So which is it? Can above algorithm (non-deterministically) enumerate all optimal solutions, or can there be hidden ones?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.