UC Santa Cruz

This thesis explores various aspects of Phylogenetic Constraint Satisfaction Problems (CSPs), focusing on their computational complexity and approximation strategies. Phylogenetic CSPs abstract problems such as Triplet and Quartet Reconstruction, which are fundamental problems in hierarchical clustering.

This thesis is structured into three distinct studies: Order-Preserving Phylogenetic CSPs, Bounded Occurrence Phylogenetic CSPs, and Random Phylogenetic CSPs. Each category looks at Phylogenetic CSPs under specific constraints and conditions. We extend Aho’s tree discovery algorithm to manage order-preserving triplet constraints, study approximation algorithms for MaxTriplets and MaxQuartets under bounded occurrence conditions, and investigate the gap between local and global satisfiability in random CSPs.

The discussion on Phylogenetic CSP throughout this thesis is based on the work of Chatziafratis and Makarychev (2023): “Since there is no algorithm better than random, what can we do?” The chapter “Order-Preserving CSPs” is based on the work of Aho, Sagiv, Szymanski, and Ullman (1981). The chapter “Bounded Occurrence CSPs” is based on the work of Makarychev (2012). The chapter “Random CSPs” is based on the work of Alon, Snir, and Yuster (2014).