Approximability of Constrained LCS

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

A

1

,...,

A

k

and

l

constraint sequences

B

1

,...,

B

l

, C-LCS(

k

,

l

) is the problem of finding a longest common subsequence of

A

1

,...,

A

k

that is also a common supersequence of

B

1

,...,

B

l

. Gotthilf et al. gave a polynomial-time algorithm that approximates C-LCS(

k

,1) within a factor

$\sqrt{\hat m |\Sigma|}$

, where

$\hat m$

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

$\sqrt{\hat m |\Sigma|}$

is in fact already very close to optimal although a small improvement is still possible:

1

For any computable function

f

and any

ε

> 0, there is no polynomial-time algorithm that approximates C-LCS

k

,1 within a factor

$f(|\Sigma|)\cdot \hat m^{1/2-\epsilon}$

unless NP = P. Moreover, this holds even if the constraint sequence is unary.

2

There is a polynomial-time randomized algorithm that approximates C-LCS (

k

,1) within a factor

$|\Sigma| \cdot O(\sqrt{{\rm OPT}\cdot\log\log{\rm OPT}/\log{\rm OPT}})$

with high probability, where OPT is the length of the optimal solution,

${\rm OPT} \le \hat m$

.

For the problem over an alphabet of arbitrary size, we show that

3.

For any

ε

> 0, there is no polynomial-time algorithm that approximates C-LCS(

k

,1) within a factor

$\hat m^{1-\epsilon}$

unless NP = SP.

4.

There is a polynomial-time algorithm that approximates C-LCS(

k

, 1) within a factor

$O(\hat m/\log\hat m)$

.

We also present some complementary results on exact and parameterized algorithms for C-LCS(

k

,

l

).