ISIPhyNC - Class: binary reticulation-visible

Definition

Relationships with other phylogenetic network classes

Maximum subclasses

• binary galled network [reference] (Lemma 6.11.14 on page 165)
• binary genetically stable [reference] (Proposition 2)

Minimum superclasses

• binary compressed [reference] (See Proposition 1(2))

Problems

Positive results proved for this class

• Cluster Containment: Solvable in O(n) time [reference]
• Tree Containment: Solvable in O(n³) time [reference]
• Tree Containment: Solvable in O(n) time [reference]
• Tree Containment: Solvable in O(n) time [reference]

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

No negative result could be deduced from subclasses.

Properties

Properties proved for this class

• Upper bound on the number of vertices: An upper bound on the number of vertices is 8n-7 and an upper bound on the number of reticulation vertices is 3n-3. Both bounds are tight. [reference] (Theorem 1.2)

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:
no network found in this class with a direct proof

Deduced from class inclusions: network #5 (deduced from the inclusion of "binary unicyclic" in this class), network #14 (deduced from the inclusion of "binary galled network" in this class), network #6 (deduced from the inclusion of "binary galled tree" in this class), network #7 (deduced from the inclusion of "binary galled network" 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 #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 #4 (deduced from the inclusion of "binary genetically stable" in this class), network #18 (deduced from the inclusion of "binary galled network" in this class), network #15 (deduced from the inclusion of "binary normal" in this class)

Not in this class

Proved directly:
network #11 : Reticulation vertex c is not stable for leaf 1 (there is a path from r to 1 containing vertex a and not containing c) nor for leaf 2 (there is a path from r to 2 containing vertex f and not containing c).
network #24 : Reticulation vertex d is not stable for leaf 2 (there is a path from r to 2 containing vertex b and not containing d) nor for leaf 3 (there is a path from r to 3 containing vertex h and not containing d).

Deduced from class inclusions: network #12 (deduced from the inclusion of this class in "binary compressed"), network #10 (deduced from the inclusion of this class in "binary tree-based"), network #3 (deduced from the inclusion of this class in "binary tree-based")