ISIPhyNC - Class: binary genetically stable

Definition

Relationships with other phylogenetic network classes

Maximum subclasses

• binary nearly tree-child

Minimum superclasses

• binary FU-stable (The class of binary genetically stable networks is a subclass of the classes of binary compressed networks and binary tree-sibling networks, which implies, according to Corollary 1 of [HMSW2016], that it is also a subclass of binary FU-stable networks.)
• binary reticulation-visible [reference] (Proposition 2)
• binary tree-sibling

Problems

Positive results proved for this class

No positive result found

Positive results deduced from superclasses

• Cluster Containment, positive result on binary reticulation-visible: Solvable in O(n) time [reference]
• 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]
• Tree Containment, positive result on binary reticulation-visible: Solvable in O(n³) time [reference]
• Tree Containment, positive result on binary reticulation-visible: Solvable in O(n) time [reference]
• Tree Containment, positive result on binary reticulation-visible: Solvable in O(n) time [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

No property found

Properties deduced from superclasses

• Upper bound on the number of vertices, property of binary reticulation-visible: 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 subclasses

No property could be deduced from subclasses.

Examples of networks

In this class

proved directly:
network #4 : All reticulation vertices are stable (e for leaf 2, d for leaf 1, g for leaf 3, j for leaf 4) and all have at least one parent which is stable (f, parent of d, stable for leaf 2; b, parent of e, stable for leaves 1 and 2; a, parent of g, stable for leaves 1 and 2; h, parent of j, stable for leaf 4)

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

Not in this class

Proved directly:
no network found outside this class with a direct proof

Deduced from class inclusions: network #14 (deduced from the inclusion of this class in "binary tree-sibling"), network #12 (deduced from the inclusion of this class in "binary compressed"), network #11 (deduced from the inclusion of this class in "binary reticulation-visible"), network #1 (deduced from the inclusion of this class in "binary tree-sibling"), network #10 (deduced from the inclusion of this class in "binary tree-based"), network #24 (deduced from the inclusion of this class in "binary reticulation-visible"), network #2 (deduced from the inclusion of this class in "binary tree-sibling"), network #3 (deduced from the inclusion of this class in "binary tree-based")