2
$\begingroup$

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 Informationenter image description here This works out to look like the below as a graph (please excuse the grid lines)

enter image description here

The part I don't understand of the proof

enter image description here

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.

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

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.

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