ISIPhyNC - Class: binary

Definition

Relationships with other phylogenetic network classes

Maximum subclasses

• binary k-reticulated
• binary nearly stable
• binary spread-k
• binary stable-child
• binary time-consistent
• binary tree-based

Minimum superclasses

No class found

Problems

Positive results proved for this class

• Phylogenetic Network Isomorphism: 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]

Positive results deduced from superclasses

No positive result could be deduced from superclasses.

Negative results proved for this class

• Cluster Containment: NP-hard, reduction from Cluster Containment in general graphs [reference] (Lemma 4.1)
• Tree Containment: NP-hard, reduction from Node-disjoint Paths [reference] (Theorem 3.1)

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)
• Tree Containment, negative result on binary spread-1: NP-complete, by a reduction from the general TreeContainment problem [reference]
• Tree Containment, negative result on binary time-consistent: NP-hard, reduction from Tree Containment on binary networks. [reference] (Theorem 3)

Properties

Properties proved for this class

No property found

Properties deduced from superclasses

No property could be deduced from superclasses.

Properties deduced from subclasses

• Completeness for reconstruction from trees, property of binary tree-based: 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.)
• Unbounded number of vertices, property of binary nested: By subdividing the arc below the root of a blob on a side which contains a leaf, subdividing the arc above the reticulation arc of the same blob on the same s, and adding an arc from the vertex created by the first subdivision to the vertex created by the second subdivision, we increase the number of arcs and vertices of the network without increasing the number of leaves, and the network remains nested.

Examples of networks

In this class

proved directly:
network #1 :

Deduced from class inclusions: network #20 (deduced from the inclusion of "binary nested" in this class), network #5 (deduced from the inclusion of "binary unicyclic" in this class), network #12 (deduced from the inclusion of "binary tree-based" in this class), network #14 (deduced from the inclusion of "binary galled network" 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 #13 (deduced from the inclusion of "binary normal" in this class), network #22 (deduced from the inclusion of "binary normal" in this class), network #9 (deduced from the inclusion of "binary level-2" in this class), network #1 (deduced from the inclusion of "binary nearly stable" in this class), network #21 (deduced from the inclusion of "binary galled network" in this class), network #10 (deduced from the inclusion of "binary level-3" in this class), network #24 (deduced from the inclusion of "binary regular" in this class), network #19 (deduced from the inclusion of "binary 3-nested" in this class), network #3 (deduced from the inclusion of "binary nearly stable" in this class), network #2 (deduced from the inclusion of "binary nearly stable" in this class), network #8 (deduced from the inclusion of "binary level-3" in this class), network #4 (deduced from the inclusion of "binary nearly stable" in this class), network #18 (deduced from the inclusion of "binary galled network" in this class), network #16 (deduced from the inclusion of "binary 2-nested" in this class), network #23 (deduced from the inclusion of "binary time-consistent" 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: no network found outside this class using class inclusions