Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00565
Tree Containment With Soft Polytomies
Vol. 25, no. 1, pp. 417436, 2021. Regular paper.
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 highdegree 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 NPcomplete, even if $N$ is a binary, multilabeled 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 2SAT instance of size $O(T^3)$. This implies NPcompleteness and polynomialtime solvability on reticulationvisible networks
in which the maximum indegree is bounded by three and two, respectively.
This work is licensed under the terms of the CCBY license.

Submitted: February 2020.
Reviewed: July 2020.
Revised: July 2020.
Accepted: March 2021.
Final: July 2021.
Published: September 2021.
Communicated by
Fabio Vandin

Journal Supporters
