Phylogenetic graph models beyond trees Original Research Article

A graph model for a set image of splits of a set image consists of a graph and a map from image to the vertices of the graph such that the inclusion-minimal cuts of the graph represent image. 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 image 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 image-complete to find a compatible subset of maximum size. Finally, we briefly discuss further generalizations of tree models.