Phylogenetic graph models beyond trees
A graph model for a set S S of splits of a set X X consists of a graph and a map from X X to the vertices of the graph such that the inclusion-minimal cuts of the graph represent S S . 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 S S 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 NP N P -complete to find a compatible subset of maximum size. Finally, we briefly discuss further generalizations of tree models.
graph models splits phylogenetic trees cactus model compatibility