We partially order a collection of genotypes so that we can represent the problem of inferring the least number of haplotypes in terms of substructures we call g-lattices. This representation allows us to prove that if the genotypes partition into chains with certain structure, then the NP-Hard problem can be solved efficiently. Even without the specified structure, the decomposition shows how to separate the underlying integer programming model into smaller models.
Holder, Allen and Langley, Thomas M., "A Decomposition of the Pure Parsimony Problem" (2009). Mathematical Sciences Technical Reports (MSTR). 15.