The Tree Labeling Polytope: A Unified Approach to Ancestral Reconstruction Problems

The small parsimony problem is a fundamental discrete optimization problem in computational biology, aiming to find the most parsimonious ancestral labeling over a fixed phylogenetic tree. Classically, the small parsimony problem is solved in O(nm²) time, where n is the number of vertices and m is the label set size, using Sankoff’s dynamic programming algorithm. However, when additional constraints are imposed upon the inferred ancestral labeling, the optimal substructure property required for Sankoff’s algorithm does not hold. To resolve this challenge, we develop a compact polyhedral description of the set of ancestral labelings, leading to a polynomial-sized linear programming formulation for the small parsimony problem. This framework not only reproduces the classical, polynomial time solution to the small parsimony problem, but also naturally accommodates additional constraints by appending linear or integer linear variables and constraints.