Longest Common Sequence reduction proof question

Question

I'm trying to get at least a laymans understanding of how the Longest Common Sequence (LCS henceforth) can be shown to be NP-Hard and I'm trying to do that by reducing it to an NP-Complete problem like Vertex Cover. I read through this downvoted question on another stack exchange.

I am trying to understand the demostration of intractability of the LCS problem, as stated as a reduction from Vertex-Cover problem, and so far, i'm stuck with the demostration of the problem in this paper from David Maier

Anybody know some simple example to reduce LCS from Vertex-Cover?

With a self answer of

It was as simple as:

• Take a Vertex-Cover problem to convert to LCS
• Create a string template from the Vertex-Cover graph
• Take each vertex from the Vertex-Cover problem and generate an equivalent string for it, ommiting the vertex selected
• Presto, you have a LCS problem equivalent.

Thanks for the downvotes

I've been trying to work out on paper how this makes sense but keep coming up against a wall. Could someone show me how this is either incorrect or how it is correct with a more worked out example/proof?

Answer 1

We can prove that LCS (with an unbounded number of sequences!) is NP-hard by reduction from 3SAT. Let us be given a CNF $\varphi$ with $m$ clauses $C_j$ of the form $$ (x_{i_{j,1}} = b_{j,1}) \lor (x_{i_{j,2}} = b_{j,2}) \lor (x_{i_{j,3}} = b_{j,3}). $$ Here $b(j,c)$ is either T or F, and we assume that $i_{j,1},i_{j,2},i_{j,3}$ are all distinct.

We will consider the following strings:

• $S_1 = x_{i_{1,1},1}^{b_{1,1}} x_{i_{1,2},1}^{b_{1,2}} x_{i_{1,3},1}^{b_{1,3}} \ldots x_{i_{m,1},m}^{b_{m,1}} x_{i_{m,2},m}^{b_{m,2}} x_{i_{m,3},m}^{b_{m,3}}$.
• $S_2 = x_{i_{1,2},1}^{b_{1,2}} x_{i_{1,3},1}^{b_{1,3}} x_{i_{1,1},1}^{b_{1,1}} \ldots x_{i_{m,2},m}^{b_{m,2}} x_{i_{m,3},m}^{b_{m,3}} x_{i_{m,1},m}^{b_{m,1}}$.
• $S_3 = x_{i_{1,3},1}^{b_{1,3}} x_{i_{1,1},1}^{b_{1,1}} x_{i_{1,2},1}^{b_{1,2}} \ldots x_{i_{m,3},m}^{b_{m,3}} x_{i_{m,1},m}^{b_{m,1}} x_{i_{m,2},m}^{b_{m,2}}$.

For each variable $x_i$, let $T_i$ be the string obtained from $S_1$ by removing all occurrences of $x_{i,j}^F$ (for all $j$), and let $F_i$ be the string obtained from $S_1$ by removing all occurrences of $x_{i,j}^T$.

• For each variable $x_i$, $TF_i = T_i F_i$ and $FT_i = F_i T_i$.

Let $R$ be a common subsequence of all these strings.

1. For every $j$, the string $R$ contains at most one of $x_{i_{j,1},j}^{b_{j,1}},x_{i_{j,2},j}^{b_{j,2}},x_{i_{j,3},j}^{b_{j,3}}$. Indeed, suppose that it contained both $x_{i_{j,k_1},j}^{b_{j,k_1}}$ and $x_{i_{j,k_2},j}^{b_{j,k_2}}$, in this order. Since $R$ is a subsequence of $S_1$, we must have $k_1 < k_2$. However, if $k_1 = 1$ then $R$ cannot be a subsequence of $S_2$, and if $k_1 = 2$ then $R$ cannot be a subsequence of $S_3$.

   • Thus $|R| \leq m$, and if $|R| = m$ then we can associate with $R$ a choice of equation in each clause.

2. For every $i$, if $R$ contains both $x_{i,j_1}^{b_1}$ and $x_{i,j_2}^{b_2}$ then $b_1 = b_2$. Indeed, in any subsequence of $TF_i$ all symbols $x_{i,j_1}^T$ precede all symbols $x_{i,j_2}^F$, and in any subsequence of $FT_i$ all symbols $x_{i,j_1}^F$ precede all symbols $x_{i,j_2}^T$.

   • Thus the chosen equations are all compatible.

This shows that if $|R| = m$ then $\varphi$ is satisfiable. The converse is also easy to establish: given a satisfying assignment, we can choose a satisfied equation in each clause, and then concatenate the corresponding symbols.

Let us give an example. Consider the formula $$ \varphi = [(x_1 = T) \lor (x_2 = T) \lor (x_3 = T)] \land [(x_2 = F) \lor (x_4=F) \lor (x_1 = F)]. $$ The strings are

• $S_1 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
• $S_2 = x_{2,1}^T x_{3,1}^T x_{1,1}^T x_{4,2}^F x_{1,2}^F x_{2,2}^F$.
• $S_3 = x_{3,1}^T x_{1,1}^T x_{2,1}^T x_{1,2}^F x_{2,2}^F x_{4,2}^F$.
• $TF_1 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
• $FT_1 = x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F$.
• $TF_2 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
• $FT_2 = x_{1,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{4,2}^F x_{1,2}^F$.
• $TF_3 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
• $FT_3 = x_{1,1}^T x_{2,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
• $TF_4 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
• $FT_4 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{1,2}^F$.

One string $R$ of length $m=2$ which is common to all of these is $x_{1,1}^T x_{2,2}^F$. This corresponds to the (partial) truth assignment $x_1=T,x_2=F$, which satisfies $\varphi$.