Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
What's the linked image for? –  Tom Leinster Sep 1 '12 at 13:48
add comment

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
    
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! –  javy1985114 Sep 3 '12 at 3:42
    
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. –  Philippe Nadeau Sep 3 '12 at 5:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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