We 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.
