ISIPhyNC - Class: binary tree-based

Definition

Relationships with other phylogenetic network classes

Maximum subclasses

• binary compressed [reference] (The parents of any reticulation vertex of a binary compressed network N are not reticulation vertices, so according to Proposition 3, N is tree-based.)
• binary level-2 [reference]
• binary tree-sibling

Minimum superclasses

• binary

Problems

Positive results proved for this class

No positive result found

Positive results deduced from superclasses

• Phylogenetic Network Isomorphism, positive result on binary: The phylogenetic network isomorphism problem can be solved in O(n⁴) time on binary networks. Simulations show that the algorithm is practical, with instances of 500 vertices solved in less than one tenth of a second. [reference]

Negative results proved for this class

No negative result found

Negative results deduced from subclasses

• Cluster Containment, negative result on binary regular: NP-hard, reduction from Cluster Containment in general graphs using:
  • the procedures to refine the vertices of degree strictly greater than 3, described in the remark in the end of the proof of Theorem 4.1 of [KNTX2008] and in the proof of Observation 2 of [FIKS2015];
  • the gadget in described in the proof of Theorem 3 of [ISS2010].
• Tree Containment, negative result on binary tree-sibling: NP-hard, reduction from Tree Containment on binary networks. [reference] (Theorem 3)
• Tree Containment, negative result on binary regular: NP-hard, reduction from Tree Containment on binary networks. [reference] (Theorem 3)

Properties

Properties proved for this class

• Completeness for reconstruction from trees: Starting with any tree T, we can build a binary tree-based network N based on it which contains all possible trees on the same set of leaves than T. The gadget consists in adding arcs just above the leaves of T. n-1 blocks of arcs must be added, where a block is a set of all possible arcs from the arc above leaf i to the arc above leaf j for i<j, added successively. [reference] (Proposition 4 provides a tree-based network which displays all trees on n leaves with O(n³) arcs.)

Properties deduced from superclasses

No property could be deduced from superclasses.

Properties deduced from subclasses

No property could be deduced from subclasses.

Examples of networks

In this class

proved directly:
network #12 : Removing the reticulation arcs (c,a) and (d,b) provides a tree this network is based on.
network #1 : Removing the reticulation arcs (f,a), (e,b) and (d,c) provides a tree this network is based on.

Deduced from class inclusions: network #5 (deduced from the inclusion of "binary unicyclic" in this class), network #14 (deduced from the inclusion of "binary compressed" in this class), network #12 (deduced from the inclusion of "binary tree-sibling" in this class), network #17 (deduced from the inclusion of "binary level-2" in this class), network #6 (deduced from the inclusion of "binary galled tree" in this class), network #11 (deduced from the inclusion of "binary FU-stable" in this class), network #7 (deduced from the inclusion of "binary galled network" in this class), network #9 (deduced from the inclusion of "binary distinct-cluster" in this class), network #13 (deduced from the inclusion of "binary normal" in this class), network #22 (deduced from the inclusion of "binary normal" in this class), network #1 (deduced from the inclusion of "binary galled network" in this class), network #21 (deduced from the inclusion of "binary galled network" in this class), network #24 (deduced from the inclusion of "binary regular" in this class), network #2 (deduced from the inclusion of "binary galled network" in this class), network #8 (deduced from the inclusion of "binary nearly tree-child" in this class), network #18 (deduced from the inclusion of "binary galled network" in this class), network #4 (deduced from the inclusion of "binary FU-stable" in this class), network #15 (deduced from the inclusion of "binary normal" in this class)

Not in this class

Proved directly:
network #10 :
network #3 : Suppose N is tree-based, and consider the tree T it is based on. If reticulation arc (c,d) is chosen in T, there would remain no leaf below h in T. A symmetric argument works for arc (h,d) and c, which leads to a contradiction.

Deduced from class inclusions: no network found outside this class using class inclusions