Approximability of constrained LCS

Abstract: The problem Constrained Longest Common Subsequence is a natural extension to the classical problem Longest Common Subsequence, and has important applications to bioinformatics. Given k input sequences and l constraint sequences , is the problem of finding a longest common subsequence of that is also a common supersequence of . Gotthilf et al. gave a polynomial-time algorithm that approximates within a factor , where is the length of the shortest input sequence and is the alphabet size. They asked whether there are better approximation algorithms and whether there exists a lower bound. In this paper, we answer their questions by showing that their approximation factor is in fact already very close to optimal although a small improvement is still possible: [1.] For any computable function f and any , there is no polynomial-time algorithm that approximates within a factor unless . Moreover, this holds even if the constraint sequence is unary. [2.] There is a polynomial-time randomized algorithm that approximates within a factor with high probability, where OPT is the length of the optimal solution, . For the problem over an alphabet of arbitrary size, we show that [3.] For any , there is no polynomial-time algorithm that approximates within a factor unless . [4.] There is a polynomial-time algorithm that approximates within a factor . We also present some complementary results on exact and parameterized algorithms for . [Copyright &y& Elsevier]