# How do I follow the text of this Longest Common Sequence proof?

I'm working through a proof that is a simplified version of David Maeirs LCS reduction from the VERTEX-COVER problem and I had a question about a specific set of instructions and how to execute them by hand.

Background Information This works out to look like the below as a graph (please excuse the grid lines)

The part I don't understand of the proof

Now I think this would imply that I need to line up S0-S7 vertically and using that rule show I can find the LCS, which was shown in my proof to be

$$00000001000000000000000000000100000000000000100000001$$ $$0^710^{21}10^{14}10^71$$

I tried doing that but was unable after many attempts to show that I could in fact induce $$Topt$$ from the sequences below. Could someone explain where I'm going wrong here? Did I misinterpret the instructions?

$$S0 =00000001000000010000000100000001000000010000000100000001$$

$$S1 =00000000000000100000000000000100000001000000010000000100000001$$

$$S2 =00000001000000000000001000000000000001000000010000000100000001$$

$$S3 =00000001000000000000001000000010000000000000010000000100000001$$

$$S4 =00000001000000010000000000000010000000100000000000000100000001$$

$$S5 =00000001000000010000000000000010000000100000001000000000000001$$

$$S6 =00000001000000010000000100000000000000100000000000000100000001$$

$$S7 =00000001000000010000000100000001000000000000001000000010000000$$

EDIT: I tried everything I could think of to see if I could make any of them work but didn't think it was relevant enough to include, if you want to know what I did I can list them.

• This process does not show an algorithm to find a lcs. – xskxzr Mar 2 '18 at 12:16

The two red-underlined parts of the proof is to standardize an LCS solution, that is called $$T_{opt}$$ therein.

The idea is to push all the $$0$$'s farthest possible to the right (without passing through its nearest $$1$$ to the right).

Consider the following two strings:

$$s_1=0001000100010001$$ (i.e. $$n=4$$ vertices)

$$s_2=0001000\ 00010001000$$ (where the space is for visualizing purpose only) (i.e. $$u=2$$, $$v=4$$)

A common subsequence (not necessarily longest) can be: $$s=0001000 00010001$$ (i.e. $$u$$ is omitted)

The standardization process in the proof is to actually align $$s$$ against $$s_1$$, $$s_2$$.

And, this MUST be standardized to be as follows:

s1= 0001 0001 0001 0001

s2= 0001 000 0001 0001000

s = 0001 000 0001 0001

Similarly, if we omit $$v$$, then $$s=000100010001000$$

And, this should be standardized as follows:

s1= 0001 0001 0001 0001

s2= 0001 000 0001 0001 000

s = 0001 0001 0001 000

Finally, we will be able to construct an $$n^2+k$$-long common subsequence if there exists an independent set of size $$n-k$$, where for each edge $$\{u,v\}$$, we omit at least one of them (the ones that are in the independent set) so that it is possible to align like we do above (note that each edge-string $$e_j$$ contains only $$n-1$$ symbol $$1$$'s). And lastly, by complementing a $$k$$-VC, we have an $$(n-k)$$-IS.