1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I suggest reading the paper (which he gave the link to) instead of following a down-voted answer. $\endgroup$ – Willard Zhan Mar 1 '18 at 5:03
  • $\begingroup$ Should I be asking for a laymans explanation of the paper instead? $\endgroup$ – Legion Daeth Mar 1 '18 at 5:58
  • $\begingroup$ I'm basically asking the same question he was. And his was downvoted for being off topic. $\endgroup$ – Legion Daeth Mar 1 '18 at 6:03
  • 1
    $\begingroup$ Can you be more specific about this 'wall' of yours? That is, where exactly are you stuck and what doesn't make sense? Unless you tell us what your specific problem is, it is unlikely we'll be able to help you. $\endgroup$ – Discrete lizard♦ Mar 1 '18 at 8:20
3
$\begingroup$

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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.