1
$\begingroup$

Let $\Sigma$ be an alphabet of some symbols, and let $\mathrm{lcs}$ denote the length of the longest common subsequence of two or more sequences defined on $\Sigma$. For some $A,B,C\in\Sigma^{\star}$, given $\mathrm{lcs}\!\left(A,B\right)$, $\mathrm{lcs}\!\left(B,C\right)$ and $\mathrm{lcs}\!\left(C,A\right)$, what can be said about $\mathrm{lcs}\!\left(A,B,C\right)$? Obviously, $\mathrm{lcs}\!\left(A,B,C\right)\leqslant \mathrm{min}\!\left\{\mathrm{lcs}\!\left(A,B\right),\mathrm{lcs}\!\left(B,C\right),\mathrm{lcs}\!\left(C,A\right)\right\}$, but what else?

The standard DP approach reduces the LCS problem to smaller LCS problems, where smaller means shorter sequences. So here I ask if it can somehow be reduced to LCS problems with fewer sequences? Any research and/or known results on this question?

$\endgroup$
8
  • 1
    $\begingroup$ Compare $A=12,B=13,C=23$ to $A=12,B=13,C=14$. $\endgroup$ Commented Mar 14, 2022 at 16:33
  • $\begingroup$ @YuvalFilmus Sorry, didn't get what you mean? $\endgroup$
    – Vahagn
    Commented Mar 14, 2022 at 17:00
  • $\begingroup$ I gave two examples in which $\mathrm{lcs}(A,B)=\mathrm{lcs}(A,C)=\mathrm{lcs}(B,C) = 1$, but in the first example $\mathrm{lcs}(A,B,C)=0$, and in the second one $\mathrm{lcs}(A,B,C)=1$. $\endgroup$ Commented Mar 14, 2022 at 18:00
  • $\begingroup$ I see. In your comment, I was reading "twelve" instead of "one, two". But anyway, there might be some tight inequalities (maybe involving the number of symbols in $\Sigma$), though the $\mathrm{lcs}$-s of pairs does not define the $\mathrm{lcs}$ of the triple. $\endgroup$
    – Vahagn
    Commented Mar 14, 2022 at 18:21
  • 1
    $\begingroup$ If $\Sigma$ is infinite, then a similar set-based construction shows that you cannot deduce anything more about $\mathrm{lcs}(A,B,C)$. $\endgroup$ Commented Mar 14, 2022 at 19:18

1 Answer 1

3
$\begingroup$

If $|\Sigma| \geq 3$, then for any non-negative integers $x \leq x_{AB}, x_{AC}, x_{BC}$ we can find strings $A,B,C$ such that $\operatorname{lcs}(A,B,C) = x$, $\operatorname{lcs}(A,B) = x_{AB}$, $\operatorname{lcs}(A,C) = x_{AC}$, $\operatorname{lcs}(B,C) = x_{BC}$: \begin{align} A &= a^x b^{x_{AC} - x} c^{x_{AB} - x} \\ B &= a^{x_{BC}} c^{x_{AB} - x} \\ C &= a^{x_{BC}} b^{x_{AC} - x} \end{align} where $a,b,c$ are different letters in $\Sigma$.

However, if $|\Sigma|=2$ and $\operatorname{lcs}(A,B) \ge 1$, $\operatorname{lcs}(A,C) \ge 1$, $\operatorname{lcs}(B,C) \ge 1$, then $\operatorname{lcs}(A,B, C) \ge 1$.

$\endgroup$
2
  • $\begingroup$ Nice construction! $\endgroup$
    – John L.
    Commented Mar 15, 2022 at 22:02
  • $\begingroup$ If $|\Sigma|=2$, $\operatorname{lcs}(A,B,C) \ge\frac12\min(\operatorname{lcs}(A,B), \operatorname{lcs}(A,C), \operatorname{lcs}(B,C))$. $\endgroup$
    – John L.
    Commented Mar 16, 2022 at 0:49

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.