Parameterized complexity and approximability of the Longest Compatible Sequence problem

AbstractWe introduce the Longest Compatible Sequence (Slcs) problem. This problem deals with p-sequences, which are strings on a given alphabet where each letter occurs at most once. The Slcs problem takes as input a collection of k p-sequences on a common alphabet L of size n, and seeks a p-sequence on L 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 Slcs problem, we derive new hardness results for the Longest Common Subsequence problem and other problems that are hard for the W-hierarchy