Zusammenfassung
The question whether a partition $\mathcal\P\$ and a hierarchy $\mathcal\H\$ or a tree-like split system $\mathfrak\S\$ are compatible naturally arises in a wide range of classification problems. In the setting of phylogenetic trees, one asks whether the sets of $\mathcal\P\$coincide with leaf sets of connected components obtained by deleting some edges from the tree $T$ that represents $\mathcal\H\$ or $\mathfrak\S\$, respectively. More generally, we ask whether a refinement $T^*$ of $T$ exists such that $T^*$ and $\mathcal\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 $\mathcal\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.
Nutzer
