Title: Perfect phylogenies via branchings in acyclic digraphs and a generalization of Dilworth's theorem,
Abstract: Motivated by applications in cancer genomics and following the work of
Hajirasouliha and Raphael (WABI 2014), Hujdurović et al. (IEEE TCBB, to
appear) introduced the minimum conflict-free row split (MCRS) problem: split
each row of a given binary matrix into a bitwise OR of a set of rows so that
the resulting matrix corresponds to a perfect phylogeny and has the minimum
possible number of rows among all matrices with this property. Hajirasouliha
and Raphael also proposed the study of a similar problem, in which the task is
to minimize the number of distinct rows of the resulting matrix. Hujdurović
et al. proved that both problems are NP-hard, gave a related characterization
of transitively orientable graphs, and proposed a polynomial-time heuristic
algorithm for the MCRS problem based on coloring cocomparability graphs.
We give new, more transparent formulations of the two problems, showing that
the problems are equivalent to two optimization problems on branchings in a
derived directed acyclic graph. Building on these formulations, we obtain new
results on the two problems, including: (i) a strengthening of the heuristic by
Hujdurović et al. via a new min-max result in digraphs generalizing
Dilworth's theorem, which may be of independent interest, (ii) APX-hardness
results for both problems, (iii) approximation algorithms, and (iv)
exponential-time algorithms solving the two problems to optimality faster than
the naïve brute-force approach. Our work relates to several well studied
notions in combinatorial optimization: chain partitions in partially ordered
sets, laminar hypergraphs, and (classical and weighted) colorings of graphs.