Radiation hybrid map construction problem parameterized

In this paper, we study the Radiation hybrid map construction ( $\mathsf{R}\mathsf{H}\mathsf{M}\mathsf{C}$ ) problem which is about reconstructing a genome from a set of gene clusters. The problem is known to be $mathsf\mathrm{NP}$ ‐complete even when all gene clusters are of size two and the corresponding problem ( ${\mathsf{R}\mathsf{H}\mathsf{M}\mathsf{C}}_{\mathsf{2}}$ ) admits efficient constant‐factor approximation algorithms. In this paper, for the first time, we consider the more general case when the gene clusters can have size either two or three ( ${\mathsf{R}\mathsf{H}\mathsf{M}\mathsf{C}}_{\mathsf{3}}$ ). Let $p\text{- }\mathsf{R}\mathsf{H}\mathsf{M}\mathsf{C}$ be a parameterized version of $\mathsf{R}\mathsf{H}\mathsf{M}\mathsf{C}$ where the parameter is the size of solution. We present a linear kernel for $p\text{- }{\mathsf{R}\mathsf{H}\mathsf{M}\mathsf{C}}_3$ of size $22k$ that when combined with a bounded search‐tree algorithm, gives an FPT algorithm running in $O(6^{k}k+n)$ time. For $p\text{- }{\mathsf{R}\mathsf{H}\mathsf{M}\mathsf{C}}_3$ we present a bounded search tree algorithm which runs in $O^{*}({2.45}^k)$ time, greatly improving the previous bound using weak kernels.