# Is there a way to determine the LCS of three based on the LCS-s of all three pairs?

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?

• Compare $A=12,B=13,C=23$ to $A=12,B=13,C=14$. Commented Mar 14, 2022 at 16:33
• @YuvalFilmus Sorry, didn't get what you mean? Commented Mar 14, 2022 at 17:00
• 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$. Commented Mar 14, 2022 at 18:00
• 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. Commented Mar 14, 2022 at 18:21
• If $\Sigma$ is infinite, then a similar set-based construction shows that you cannot deduce anything more about $\mathrm{lcs}(A,B,C)$. Commented Mar 14, 2022 at 19:18

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$$.
• If $|\Sigma|=2$, $\operatorname{lcs}(A,B,C) \ge\frac12\min(\operatorname{lcs}(A,B), \operatorname{lcs}(A,C), \operatorname{lcs}(B,C))$. Commented Mar 16, 2022 at 0:49