摘要
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 <inline-formula><tex-math notation="LaTeX"> m \times n </tex-math></inline-formula> binary matrix <inline-formula><tex-math notation="LaTeX"> M </tex-math></inline-formula> is given. A split-row operation on <inline-formula><tex-math notation="LaTeX"> M </tex-math></inline-formula> is defined as replacing a row <inline-formula><tex-math notation="LaTeX"> r </tex-math></inline-formula> by <inline-formula><tex-math notation="LaTeX"> k > 1 </tex-math></inline-formula> rows whose bitwise OR is equal to <inline-formula><tex-math notation="LaTeX"> r </tex-math></inline-formula>. The cost of the operation is the number of additional rows induced, that is, <inline-formula><tex-math notation="LaTeX"> k - 1 </tex-math></inline-formula>. The objective is to find a sequence of operations that transforms <inline-formula><tex-math notation="LaTeX"> M </tex-math></inline-formula> 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 <inline-formula><tex-math notation="LaTeX"> {\rm{\varepsilon }}( M ) </tex-math></inline-formula> denote the minimum total cost. In this paper, we show that SR admits a polynomial size kernel, which has at most <inline-formula><tex-math notation="LaTeX"> 3{\rm{\varepsilon }}( M ) </tex-math></inline-formula> rows and <inline-formula><tex-math notation="LaTeX"> 4{\rm{\varepsilon }}( M ) - 1 </tex-math></inline-formula> columns. Our kernelization algorithm requires <inline-formula><tex-math notation="LaTeX"> O( {\max ( {{{m}^{0.373}}{{n}^2}, m{{n}^{1.373}}} )} ) </tex-math></inline-formula> time. When <inline-formula><tex-math notation="LaTeX"> \varepsilon ( M ) </tex-math></inline-formula> is small, it can be used as a preprocessing procedure to speed up all previous exact algorithms for SR.
