Welcome to MathOverflow

Question

4

2

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.

edited Jul 19 2011 at 3:44

asked Jul 18 2011 at 17:45

Vamsik
41●4

Tsuyoshi Ito · Answer 1 · 2011-07-18 23:34:34Z UTC

8

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 s₁,…,s_n∈{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

answered Jul 18 2011 at 23:34

Tsuyoshi Ito
1,349●6●15

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

1

@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

Computing Simultaneous Hamming Neighborhood for a Set of Strings

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.