ISIPhyNC - Class: binary nearly stable

Definition

Relationships with other phylogenetic network classes

Maximum subclasses

• binary tree-child [reference] (Noting that binary tree-child networks can be defined as binary phylogenetic networks whose vertices are all stable implies that binary tree-child networks are particular cases of nearly-stable networks.)

Minimum superclasses

• binary

Problems

Positive results proved for this class

• Tree Containment: Solvable in O(n²) time [reference]
• Tree Containment: Solvable in O(n log 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 26n-24. [reference] (Theorem 2 (adding the number of reticulation vertices, tree vertices, the root and the leaves))
• 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 5.5 and Table 1)

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 #1 : Vertices a, f and g are stable for leaf 1; vertex b is stable for leaf 2; vertex c is stable for leaf 3; vertices e and d are not stable but their respective parents f and g are.
network #3 : Reticulation vertices c and d are the only ones which are not stable but in both cases, both their parents are.
network #2 : The unique parents of the only vertices which are not stable, d and e, respectively b and a, are stable.
network #4 : All vertices except c and i (whose unique parent is in both cases stable) are stable.

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 #15 (deduced from the inclusion of "binary normal" in this class)

Not in this class

Proved directly:
network #17 : Vertex b is not stable and its parent d is not either.
network #21 : Vertex d is not stable and its parent b is not either.
network #19 : Vertex e is not stable and its parent d is not either.
network #8 : Vertex e is not stable and its parent d is not either.

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