ISIPhyNC - Class: binary tree-child

Definition

Relationships with other phylogenetic network classes

Maximum subclasses

• binary galled tree [reference] (A detailed proof is given in Lemma 6.11.11 of this book.)
• binary normal

Minimum superclasses

• binary nearly stable [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.)
• binary nearly tree-child
• binary stable-child (For any internal vertex v of a tree-child network, we consider a directed path starting from v, obtained in the following way: among the children of the lowest vertices of the path built so far, one is a tree-child, so we add it to the path. The path eventually reaches a leaf l, and the child c of v contained by this path is stable for l as there is no reticulation vertex on the path from c to l.)

Problems

Positive results proved for this class

• Tree Containment: Solvable in polynomial time [reference] (Theorem 1)

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 nearly stable: Solvable in O(n²) time [reference]
• Tree Containment, positive result on binary nearly stable: Solvable in O(n log n) time [reference]
• Tree Containment, positive result on binary nearly stable: 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]
• 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

• Upper bound on the number of vertices: An upper bound on the number of vertices is 5n-2. [reference] (Proof of Theorem 2)

Properties deduced from superclasses

• Upper bound on the number of vertices, property of binary nearly tree-child: An upper bound on the number of vertices is 4n. [reference] (Lemma 4)
• Upper bound on the number of vertices, property of binary nearly stable: 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, property of binary nearly stable: 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)
• 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)
• Upper bound on the number of vertices, property of binary stable-child: An upper bound on the number of vertices is 16n-15 and an upper bound on the number of reticulation vertices is 7n-7. Both bounds are tight. [reference] (Theorem 6.4 and Table 1)

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

Deduced from class inclusions: network #17 (deduced from the inclusion of this class in "binary nearly stable"), 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 #21 (deduced from the inclusion of this class in "binary nearly stable"), 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 #19 (deduced from the inclusion of this class in "binary nearly stable"), network #8 (deduced from the inclusion of this class in "binary nearly stable"), 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"), network #4 (deduced from the inclusion of this class in "binary nearly tree-child")