Let $\Sigma$ be the alphabet, $0<R<n$ be an integer and let $\Sigma^n$ denote the set of all strings of length $n$ over the alphabet. The task is to find the minimum $m$ such that there exist strings $S=\{s_1, \dots, s_m\}\subseteq \Sigma^n$ that satisfy: $$\forall x\in \Sigma^n\;\; \exists y\in S\colon ED(x,y)\le R$$ In other words, we want to minimize $|S|$, such that any string of length $n$ can be constructed from them with at most $R$ edit operation.

Let $S^\star$ denote one optimal solution. My guess is that an algorithm computing an optimal solution is not efficient, and likely to grow as a function of $|\Sigma|^n$. My question is, is it possible to compute an approximate solution, say satisfying $|S|\le 2|S^\star|$, in time polynomial in input size $\mathrm{Poly}(|\Sigma|,m,n)$?

  • 1
    $\begingroup$ Interesting question. One thing that might make this tricky is that there's certainly a P/poly algorithm for this (the advice for $n$ records the optimal $m$), and it might be a bit delicate to distinguish between P vs P/poly. It might be that this is more of a question about math than about algorithms (i.e., maybe you need a construction of such a set $S$ that you can prove 2-optimal, and the challenge is in identifying/proving the construction rather than in finding an algorithm to compute it.) $\endgroup$
    – D.W.
    Jan 17 '20 at 19:57

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.