direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Tree Containment with Soft Polytomies

Matthias Bentert (TU Berlin)

The Tree Containment 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 Soft Tree Containment, is NP-hard,
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-hardness and polynomial-time solvability on reticulation-visible
networks in which the maximum in-degree is bounded by three and two, respectively.



Matthias Bentert
TEL 512

Back to the research colloquium site.

Nach oben

Zusatzinformationen / Extras