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?


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


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