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?


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.