0
$\begingroup$

Basically, its a 2-sequence longest common sub-sequence (LCS) problem.

What's so special?

1: each alphabet only occurs 2 times, one in each sequence, which means with no same alphabet in one sequence.

2: we can execute 2 (or k) "LCS"es at a time, and we want the sum length of the 2 "LCS"es is the maximum.

Take the figure in the link for example.

1: when with only 1 LCS, we would run as 1-2-3-4-5-6, which length is 6.

2: but now, we have 2 LCSes, we can run one as 1-2-3-4-8, the other as 7-5-6, so the sum length is 5+3=8. Clearly, it is the optimal (maximum) in this example.

How can I do this? With multiple LCSes, and want to maximum the sum length of these LCSes?

Is this problem a NP-complete?

Thanks so much!

~~A~~B~~C~~D~~E~~F~~G~~H

A..1............................................

B........2......................................

D.................... 3.........................

E...........................4...................

H.............................................. 8

C..............7................................

F...................................5...........

G........................................6......

![LCS figure][1]

http://img2.ph.126.net/gWr2LnyNTpLmTuqjbRwrcw==/6597825131144291222.jpg

$\endgroup$
1
  • $\begingroup$ What's the linked image for? $\endgroup$ Sep 1, 2012 at 13:48

1 Answer 1

0
$\begingroup$

If one sequence is $(a_1,\ldots, a_n)$ with all $a_i$ distinct, then the other one is a permutation of it of the form $(a_{w(1)},\ldots, a_{w(n)})$. A common subsequence corresponds therefore to an increasing subsequence of the permutation $(w(1),\ldots,w(n))$.

Now the maximal total length of $k$ disjoint increasing subsequences of a permutation $w$ is given by the sum of the first $k$ parts in the shape associated to $w$ by the Schensted correspondence (this is Greene’s theorem), so this is easy to determine. I suppose there are also efficient algorithms to compute some optimal set of increasing subsequences.

$\endgroup$
2
  • $\begingroup$ Hi, Philippe Nadeau, thanks so much for your comments! It benefit me a lot! I tried some simple examples just now, and the results show that the method is optimal for k=2. say the sum of first k parts as you said. Do you think the method is also optimal for any value of k? The method seems to be so greedy, so I am afraid it becomes sub-optimal when k gets larger. Thanks so much! $\endgroup$ Sep 3, 2012 at 3:42
  • $\begingroup$ The method is a theorem: the best possible value for the sum length of k disjoint increasing subsequences is exactly the sum of the first k parts of the shape given by the Schensted correspondence. This is in C. Greene, "An extension of Schensted's theorem", Adv. in Math. 1974. I checked this article, and in fact Greene also indicates how to find an optimal set of sequences achieving this value if that's what you're interested in. $\endgroup$ Sep 3, 2012 at 5:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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