<p>It was as simple as:</p>

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

<p>Thanks for the downvotes</p>

CC BY-SA 3.0
2015-06-25T16:33:45.890Z
2015-06-25T16:33:45.890Z
Jhonny D. Cano -Leftware-
<p>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 <a href="http://dl.acm.org/citation.cfm?id=322075" rel="nofollow">David Maier</a></p>

<p>Anybody know some simple example to reduce LCS from Vertex-Cover?</p>

CC BY-SA 3.0
2015-06-25T16:30:34.507Z
nobody knows, everybody downvotes
Jhonny D. Cano -Leftware-
<np-complete>
How to reduce LCS from Vertex-Cover
Jhonny D. Cano -Leftware-
# How to reduce LCS from Vertex-Cover

(Asked by: username_0 on 2015-06-16)

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](http://dl.acm.org/citation.cfm?id=322075)

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

**Tags:** np-complete
> **Comments:**
> **username_0**: nobody knows, everybody downvotes  

---

## 1 answers

### Answer by username_0 on 2015-06-25. Score: -2 | Accepted answer

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


---

