A simple characterization of the minimal obstruction sets for three-state perfect phylogenies

We give a characterization of the minimal obstruction sets for the existence of a perfect phylogeny for a set of three-state characters that can be inferred by testing each pair of characters. This leads to a O(m2n+p)O(m2n+p) time algorithm for outputting all pp minimal obstruction sets for a set of mm three-state characters over a set of nn taxa.