4
$\begingroup$

Let $S = \lbrace s_1, s_2 \ldots s_n \rbrace$ be a set of strings each of length $k$ from an alphabet $\Sigma$, $h(s_i, s_j)$ denote the hamming distance between two strings. The simultaneous hamming neighborhood is defined as $N_{\alpha} = \lbrace s' | h(s',s_j) \leq \alpha, \forall s_j \in S , s' \in \Sigma^k \rbrace$, $1\leq \alpha \leq k$.

I would like to know if this problem (i.e. computing $N_{\alpha}$ efficiently) has been considered earlier ? -- By efficiently I mean the running time of the algorithm should be something like $O(|N_{\alpha}|)$, when $|N_{\alpha}|$ is much larger than $n$.

Thank you very much for your help.

$\endgroup$

1 Answer 1

8
$\begingroup$

I assume that you require the running time of an algorithm to be polynomial also in k. Then this is impossible even with the binary alphabet unless P=NP by the result by Frances and Litman [FL97].

Consider the easier task of deciding, given k-bit strings s1,…,sn∈{0,1}k and an integer α, whether Nα contains any element or not. This problem is equivalent to what is called the Minimum Radius problem in [FL97], where it is proved to be NP-complete.

[FL97] M. Frances and A. Litman. On covering problems of codes. Theory of Computing Systems, 30(2):113–119, March 1997. http://dx.doi.org/10.1007/BF02679443

$\endgroup$
7
  • $\begingroup$ Hello Tsuyoshi, Thank you for that reference its useful. However I'm interested in the complexity when $k$ is a fixed constant. Thank you, Vamsi. $\endgroup$ Jul 18, 2011 at 23:53
  • $\begingroup$ @Vamsik: If k is fixed, then it is straightforward to check all k-letter strings in poly(n) time because, as long as every letter in Σ appears in some string s_i, there are only |Σ|^k≤(kn)^k=poly(n) strings of length k. The case where Σ contains unused letters can be also handled easily. $\endgroup$ Jul 19, 2011 at 0:41
  • $\begingroup$ @Tsuyoshi: $\Sigma$ is part of input, so any bivariate polynomial in $n$ and $\Sigma$ would be efficient. On the other hand if $\Sigma$ were to be constant I'm wondering if exists is an $O(|N_{\alpha}|)$ algorithm. $\endgroup$ Jul 19, 2011 at 0:44
  • $\begingroup$ @Vamsik: If you fix k and you are fine with a polynomial in n and |Σ|, then check all the k-letter strings. There are |Σ|^k = poly(|Σ|) strings, and each string can be tested in poly(n) time for membership in N_α, which means that this algorithm runs in poly(n,|Σ|) time. $\endgroup$ Jul 19, 2011 at 0:49
  • 1
    $\begingroup$ @Vamsik: (1) In that case, it is trivially impossible because you have to distinguish between the case where N_α is empty and the case where |N_α|≤100 (say) in a constant time, in which you cannot even read the whole input. (2) Even if you change the question again, I will no longer try to answer. I cannot keep chasing the moving target. $\endgroup$ Jul 19, 2011 at 2:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.