Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00565
Tree Containment With Soft Polytomies
Vol. 25, no. 1, pp. 417-436, 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 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.
This work is licensed under the terms of the CC-BY 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
|