Tree Containment With Soft Polytomies

Abstract

The ${\rm T{\small REE}~C{\small ONTAINMENT}}$ problem has many important applications in the study of evolutionary history. Given a phylogenetic network $N$ and a phylogenetic tree $T$ whose leaves are labeled by a set of taxa, it asks if $N$ and $T$ are consistent. While the case of binary $N$ and $T$ has received considerable attention, the more practically relevant variant dealing with biological uncertainty has not. Such uncertainty manifests itself as high-degree vertices ("polytomies") that are "jokers" in the sense that they are compatible with any binary resolution of their children. Contrasting the binary case, we show that this problem, called ${\rm S{\small OFT}~T{\small REE}~C{\small ONTAINMENT}}$, is NP-complete, even if $N$ is a binary, multi-labeled tree in which each taxon occurs at most thrice. On the other hand, we reduce the case that each label occurs at most twice to solving a 2-SAT instance of size $O(|T|^3)$. This implies NP-completeness and polynomial-time solvability on reticulation-visible networks in which the maximum in-degree is bounded by three and two, respectively.