ISIPhyNC - Class: binary FU-stable

Definition

Relationships with other phylogenetic network classes

Maximum subclasses

• binary distinct-cluster (Suppose by contradiction there exists a network N which is binary distinct-cluster but not FU-stable. Then either it contains two vertices u and v with the same sets of children, but then they also have the same cluster, even after any contraction of an arc from a hybrid vertex to its tree-node child. Or it contains a hybrid vertex u with a hybrid parent v, which both have the same cluster, even after any contraction of an arc from a hybrid vertex to its tree-node child.)
• binary genetically 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.)

Minimum superclasses

• binary compressed

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

No negative result found

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 regular: 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

No property could be deduced from subclasses.

Examples of networks

In this class

proved directly:
network #11 : No reticulation vertex has a reticulation vertex as its parent, and no two vertices have the same sets c(u) and c(v) of children: c(r)={a,f}, c(a)={b,c}, c(b)={1}, c(c)={d}, c(d)={b,e}, c(e)={2}, c(f)={e}.
network #1 : No reticulation vertex has a reticulation vertex as its parent, and no two vertices have the same set of children
network #4 :

Deduced from class inclusions: network #5 (deduced from the inclusion of "binary unicyclic" in this class), network #9 (deduced from the inclusion of "binary distinct-cluster" 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 #24 (deduced from the inclusion of "binary regular" in this class), network #2 (deduced from the inclusion of "binary regular" in this class), network #8 (deduced from the inclusion of "binary regular" in this class), network #4 (deduced from the inclusion of "binary genetically stable" in this class), network #15 (deduced from the inclusion of "binary normal" in this class)

Not in this class

Proved directly:
network #14 : Vertices a and d have the same set of children: {b, c}.

Deduced from class inclusions: network #12 (deduced from the inclusion of this class in "binary compressed"), 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")