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 ( m 2 n + p ) time algorithm for outputting all p minimal obstruction sets for a set of m three-state characters over a set of n taxa.