Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems

In this paper, we present a survey of the approximability and fixed-parameter tractability results for some Exemplar Genomic Distance problems. We mainly focus on three problems: the exemplar breakpoint distance problem and its complement (i.e., the exemplar non-breaking similarity or the exemplar adjacency number problem), and the maximal strip recovery (MSR) problem. The following results hold for the simplest case between only two genomes (genomic maps)

${\cal G}$

and

${\cal H}$

, each containing only one sequence of genes (gene markers), possibly with repetitions.

1

For the general Exemplar Breakpoint Distance problem, it was shown that deciding if the optimal solution value of some given instance is zero is NP-hard. This implies that the problem does not admit any approximation, neither any FPT algorithm, unless P=NP. In fact, this result holds even when a gene appears in

${\cal G}$

(

${\cal H}$

) at most two times.

1

For the Exemplar Non-breaking Similarity problem, it was shown that the problem is linearly reducible from Independent Set. Hence, it does not admit any factor-

O

(

n

ε

) approximation unless P=NP and it is W[1]-complete (loosely speaking, there is no way to obtain an

O

(

n

o

(

k

)

) time exact algorithm unless FPT=W[1], here

k

is the optimal solution value of the problem).

1

For the MSR problem, after quite a lot of struggle, we recently showed that the problem is NP-complete. On the other hand, the problem was previously known to have a factor-4 approximation and we showed recently that it admits a simple FPT algorithm which runs in

O

(2

2.73

k

n

 + 

n

2

) time, where

k

is the optimal solution value of the problem.