In biology, the ancestral relations among a set of species with a common ancestor are described by a phylogenetic tree (also known as a phylogeny). Given a set of species that are described in terms of their characteristics (in matrix form), the Perfect Phylogeny problem (PP) asks whether there is a phylogeny that is consistent with respect to these characteristics. In graph terms, this question asks whether a given graph can be made chordal (or "triangulated") by adding edges under certain constraints.

A problem that is perhaps more familiar to LANS is the Acyclic Coloring problem (AC), which models the efficient computation of sparse Hessian matrices using substitution-based methods. Both of these problems are NP-complete in the general case, and remain so even under severe restrictions.

In this talk, I will demonstrate positive algorithmic results for both the PP and AC problems by means of a deep connection involving the tree structure of chordal graphs and the powerful notion of treewidth. These results include constructive, polynomial-time algorithms when the input graph belongs to the relatively large class of weakly chordal graphs, which generalizes a number of known results.

Though I will assume some familiarity with basic graph-theoretic concepts, I will not assume any knowledge of evolutionary biology.