ISIPhyNC - Class: binary regular

Definition

Relationships with other phylogenetic network classes

Maximum subclasses

• binary normal

Minimum superclasses

• binary distinct-cluster (A Hasse diagram of a family F of subsets of X does not contain two vertices corresponding to the same set of F, so a regular network does not contain two vertices with the same cluster.)

Problems

Positive results proved for this class

No positive result found

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

• Cluster Containment: 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: NP-hard, reduction from Tree Containment on binary networks. [reference] (Theorem 3)

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 2ⁿ. [reference] (Theorem 5.1(3), with a multiplication by 2 to take into account the number of vertices possibly added during the "decontraction" to obtain a binary phylogenetic network)

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 #24 : If we contract each reticulation vertex of this network with its child, we obtain the Hasse diagram of {{1},{2},{3},{4},{1,2},{2,3},{3,4},{1,2,3},{2,3,4},{1,2,3,4}}.
network #2 : If we contract each reticulation vertex of this network with its child, we obtain the Hasse diagram of {{1},{2},{3},{4},{5},{1,2},{2,3},{1,2,3},{3,4},{1,2,3,4},{4,5},{1,2,3,4,5}}.
network #8 : If we contract each reticulation vertex of this network with its child, we obtain the Hasse diagram of {{1},{2},{3},{4},{5},{1,2},{2,3},{3,4},{2,3,4},{3,4,5},{1,2,3,4},{1,2,3,4,5}}.

Deduced from class inclusions: 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 #9 : c(b)={2,3} is contained in c(e)={2,3,4}, however there is no path from e to b.

Deduced from class inclusions: network #5 (deduced from the inclusion of this class in "binary distinct-cluster"), network #14 (deduced from the inclusion of this class in "binary FU-stable"), network #12 (deduced from the inclusion of this class in "binary compressed"), network #6 (deduced from the inclusion of this class in "binary distinct-cluster"), network #11 (deduced from the inclusion of this class in "binary distinct-cluster"), network #1 (deduced from the inclusion of this class in "binary distinct-cluster"), 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"), network #4 (deduced from the inclusion of this class in "binary distinct-cluster")