ISIPhyNC - Problem: Tree Containment
Summary
Does the input network contain the input tree on the same set of leaves? [reference]
Bibliographic references on the Who is who in phylogenetic networks
More formally
Input: A phylogenetic network N and a tree T on the same set X of taxa.
Output: YES if N contains T, NO otherwise.
Phylogenetic network classes with results on this problem
Positive results
- binary level-2: Solvable in O(n) time [reference] (Observation 1)
- binary level-3: Solvable in O(n) time [reference] (Observation 1)
- binary level-k: Solvable in O(2k.n) time [reference] (Observation 1)
- binary nearly stable: Solvable in O(n2) time [reference]
- binary nearly stable: Solvable in O(n log n) time [reference]
- binary nearly stable: Solvable in O(n) time [reference]
- binary normal: Solvable in polynomial time [reference] (Theorem 2)
- binary reticulation-visible: Solvable in O(n3) time [reference]
- binary reticulation-visible: Solvable in O(n) time [reference]
- binary reticulation-visible: Solvable in O(n) time [reference]
- binary tree-child: Solvable in polynomial time [reference] (Theorem 1)
Negative results
- binary: NP-hard, reduction from Node-disjoint Paths [reference] (Theorem 3.1)
- binary regular: NP-hard, reduction from Tree Containment on binary networks. [reference] (Theorem 3)
- binary spread-1: NP-complete, by a reduction from the general TreeContainment problem [reference]
- binary time-consistent: NP-hard, reduction from Tree Containment on binary networks. [reference] (Theorem 3)
- binary tree-sibling: NP-hard, reduction from Tree Containment on binary networks. [reference] (Theorem 3)
All classes
In the inclusion diagram below, the names of classes with positive results on this problem are colored green and the name of the classes with negative results are colored red. Classes with both positive and negative results are colored yellow.
About this website
This website was programmed and is maintained by Philippe Gambette. It was started during the internship of Maxime Morgado at LIGM, in June-July 2015, and also contains contributions made from Narges Tavassoli from November 2016 to January 2017.
Please contact Philippe Gambette if you have any suggestions about this website, especially about problems, properties, results or subclasses to add.
How to cite
P. Gambette, M. Morgado, N. Tavassoli & M. Weller (2018) ISIPhyNC, an Information System on Inclusions of Phylogenetic Network Classes, manuscript in preparation.
Database content
73 classes of phylogenetic networks including 35 classes of binary phylogenetic networks (defined in a total of 20 bibliographic references), 51 inclusion relationships proved directly between classes (including some found in a total of 9 bibliographic references), 24 networks (68 memberships to a class, 56 non-memberships to a class), 3 problems considered, 3 properties considered, 37 theorems proved directly (including some found in a total of 17 bibliographic references) including 26 positive results (which can be extended to subclasses) and 11 negative results (which can be extended to superclasses).
