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) and , 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 ( ) 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(22.73k n + n 2) time, where k is the optimal solution value of the problem.