MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Computing Simultaneous Hamming Neighborhood for a Set of Strings

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.

-

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

-
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. – Vamsik Jul 18 2011 at 23:53
@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. – Tsuyoshi Ito Jul 19 2011 at 0:41
@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. – Vamsik Jul 19 2011 at 0:44
@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. – Tsuyoshi Ito Jul 19 2011 at 0:49
@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. – Tsuyoshi Ito Jul 19 2011 at 2:43
show 2 more comments