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?


closed as off-topic by Sasho Nikolov, R B, Mohammad Al-Turkistany, Kaveh, Jeffε Jun 25 '15 at 22:25

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Sasho Nikolov, R B, Mohammad Al-Turkistany, Kaveh, Jeffε
If this question can be reworded to fit the rules in the help center, please edit the question.


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.