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

Improve this question
$\endgroup$
1
  • $\begingroup$ What's the linked image for? $\endgroup$
    – Tom Leinster
    Commented Sep 1, 2012 at 13:48

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – javy1985114
    Commented 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$
    – Philippe Nadeau
    Commented Sep 3, 2012 at 5:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .