A Kernelization Algorithm for Finding a Perfect Phylogeny From Mixed Tumor Samples

The split-row problem (SR), introduced by Hajirasouliha and Raphael [WABI 2014], models an effective method for reconstructing a perfect phylogeny from mixed tumor samples. In this problem, an $m \times n$ binary matrix $M$ is given. A split-row operation on $M$ is defined as replacing a row $r$ by $k > 1$ rows whose bitwise OR is equal to $r$. The cost of the operation is the number of additional rows induced, that is, $k - 1$. The objective is to find a sequence of operations that transforms $M$ into a matrix corresponding to a perfect phylogeny and the total cost is minimized. Hujdurović et al. [TCBB 2018] proved the NP-hardness of SR. Let ${\rm{\varepsilon }}( M )$ denote the minimum total cost. In this paper, we show that SR admits a polynomial size kernel, which has at most $3{\rm{\varepsilon }}( M )$ rows and $4{\rm{\varepsilon }}( M ) - 1$ columns. Our kernelization algorithm requires $O( {\max ( {{{m}^{0.373}}{{n}^2}, m{{n}^{1.373}}} )} )$ time. When $\varepsilon ( M )$ is small, it can be used as a preprocessing procedure to speed up all previous exact algorithms for SR.