License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2018.9
URN: urn:nbn:de:0030-drops-88353
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8835/
Go to the corresponding LIPIcs Volume Portal

Bentert, Matthias ; Malík, Josef ; Weller, Mathias

Tree Containment With Soft Polytomies

pdf-format:
LIPIcs-SWAT-2018-9.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{bentert_et_al:LIPIcs:2018:8835,
  author =	{Matthias Bentert and Josef Mal{\'i}k and Mathias Weller},
  title =	{{Tree Containment With Soft Polytomies}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm  Theory (SWAT 2018)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{David Eppstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8835},
  URN =		{urn:nbn:de:0030-drops-88353},
  doi =		{10.4230/LIPIcs.SWAT.2018.9},
  annote =	{Keywords: Phylogenetics, Reticulation-Visible Networks, Multifurcating Trees}
}

Keywords: Phylogenetics, Reticulation-Visible Networks, Multifurcating Trees
Collection: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Issue Date: 2018
Date of publication: 04.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI