We consider the following problem: Given n genotypes, does there exist a set H of haplotypes such that each genotype is generated by a pair from this set, and this det can be derived on a perfect phylogeny. Recently, Gusfield, 2002, presented a polynomial time algorithm to solve this problem that uses established results from matroid and graph theory. In this work, we present an O(nm2) algorithm for this problem using elementary techniques. We also describe a linear space representation for representing all possible solutions, and provide a formula for counting the number of possible solutions.
