Parameterized complexity and approximability of the Longest Compatible Sequence problem

We introduce the Longest Compatible Sequence (SlcsSlcs) problem. This problem deals with p-sequences  , which are strings on a given alphabet where each letter occurs at most once. The SlcsSlcs problem takes as input a collection of kk pp-sequences on a common alphabet LL of size nn, and seeks a pp-sequence on LL which respects the precedence constraints induced by each input sequence, and is of maximal length with this property. We investigate the parameterized complexity and the approximability of the problem. As a by-product of our hardness results for the SlcsSlcs problem, we derive new hardness results for the Longest Common Subsequence problem and other problems that are hard for the W-hierarchy.