2
$\begingroup$

I am trying to understand an algorithm for solving Closest String using bounded search trees, as found in Parameterized Algorithms (Cygan et al., 2015).

Assume we have a set of $k$ strings $x_1, ..., x_k$ all of length $L$ and an integer $d$. The problem is to determine if there exists a string $y$ such that $d_H(y, x_i) \leq d$ for all input strings $x_i$, where $d_H$ is the Hamming distance. If this is the case, $y$ is known as a center string.

The algorithm goes as follows - I'm going fast since I'm assuming the reader knows about it, just to make sure we're on the same page:

  1. Organize the input strings into a $k \times L$ matrix. If any columns in this matrix have the same character for all strings, delete them, as they are an obvious choice for a solution.

1.5. <we may already be done if the matrix ends up large or small enough>

  1. Let $z = x_1$. If $z$ is a center string, we are done. If $z$ is not a center string, then there exists an $x_i$ with $d_H(x_i, z) > d$, so there are at least $d + 1$ positions where $x_i$ and $z$ differ. If a (hypothetical) string $y$ is a center string, then there is at least one position where $x_i$ and $y$ are the same. So we can pick $d + 1$ of these positions and recurse with a modified $z$ such that $z[p] = x_i[p]$ for each of these positions - for at least one of these $x_i[p]$ must be equal to $y[p]$. Since each level of recursion has at least one branch that brings $z$ closer to $y$, we will reach $y$ after $d$ steps (assuming it exists).

Now the complexity of this is supposed to be $\mathcal{O}(kL + kd(d + 1)^d)$. The $kL$ is for step 1. We can only recurse $d$ times, with $d + 1$ children at each level, that's where the $(d + 1)^d$ comes from. That leaves $kd$ as the time cost of step 2 at each node.

But how is the task of 1. checking whether $z$ is a center string and 2. picking out the $x_i$ and the $d + 1$ positions supposed to be doable in $\mathcal{O}(kd)$? After deleting the trivial columns in step one, our matrix is up to $kd$ columns wide. So comparing $z$ to $x_i$ for each $i$ requires iterating over up to $kd$ characters, leading to $\mathcal{O}(k^2d)$. We cannot make any assumptions about the content of the matrix - the strings could all be identical, the instance could be unsolvable, it could be just-barely solvable - only that its width is between $k + 1$ and $kd$. How does one come up with this complexity? Or have I misunderstood the complexity bound they gave?

$\endgroup$

1 Answer 1

1
$\begingroup$

Please see Theorem 1 from the original paper. The distance of $z$ to $x_i$'s can be updated in $O(k)$ time.

Note that $z$ might not necessarily be chosen from the given set of strings $x_1 , \dotsc, x_k$. So, the algorithm change the string $z$ at one position at each step of the recursion. Since only one alphabet is changed, its distance to a particular string can be updated in $O(1)$ time.

$\endgroup$
1
  • 1
    $\begingroup$ Ah, so one computes the distances from $z$ to all other strings before starting the recursion and can then update them incrementally at each step in linear time. Thanks! $\endgroup$ Commented Jun 1, 2023 at 16:23

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.