Compatibility of partitions with trees, hierarchies, and split systems

The question whether a partition P and a hierarchy H or a tree-like split system S are compatible naturally arises in a wide range of classification problems. In the setting of phylogenetic trees, one asks whether the sets of P coincide with leaf sets of connected components obtained by deleting some edges from the tree T that represents H or S, respectively. More generally, we ask whether a refinement T* of T exists such that T* and P are compatible in this sense. The latter is closely related to the question as to whether there exists a tree at all that is compatible with P. We report several characterizations for (refinements of) hierarchies and split systems that are compatible with (systems of) partitions. In addition, we provide a linear-time algorithm to check whether refinements of trees and a given partition are compatible. The latter problem becomes NP-complete but fixed-parameter tractable if a system of partitions is considered instead of a single partition. In this context, we also explore the close relationship of the concept of compatibility and so-called Fitch maps.