Phylogenetic graph models beyond trees

A graph model for a set SS of splits of a set XX consists of a graph and a map from XX to the vertices of the graph such that the inclusion-minimal cuts of the graph represent SS. Phylogenetic trees are graph models in which the graph is a tree. We show that the model can be generalized to a cactus (i.e. a tree of edges and cycles) without losing computational efficiency. A cactus can represent a quadratic rather than linear number of splits in linear space. We show how to decide in linear time in the size of a succinct representation of SS whether a set of splits has a cactus model, and if so construct it within the same time bounds. As a byproduct, we show how to construct the subset of all compatible splits and a maximal compatible set of splits in linear time. Note that it is NPNP-complete to find a compatible subset of maximum size. Finally, we briefly discuss further generalizations of tree models.