ISIPhyNC - Class: binary spread-1

Definition

Relationships with other phylogenetic network classes

Maximum subclasses

• binary leaf outerplanar [reference]

Minimum superclasses

• binary spread-2

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

• Tree Containment: NP-complete, by a reduction from the general TreeContainment problem [reference]

Negative results deduced from subclasses

No negative result could be deduced from subclasses.

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 #9 : Consider the order 1 2 3 4 of the leaves to obtain spread 1.

Deduced from class inclusions: network #5 (deduced from the inclusion of "binary unicyclic" in this class), network #12 (deduced from the inclusion of "binary leaf outerplanar" in this class), network #6 (deduced from the inclusion of "binary galled tree" in this class), network #11 (deduced from the inclusion of "binary leaf outerplanar" in this class), network #13 (deduced from the inclusion of "binary leaf outerplanar" in this class), network #1 (deduced from the inclusion of "binary leaf outerplanar" in this class), network #10 (deduced from the inclusion of "binary leaf outerplanar" in this class), network #2 (deduced from the inclusion of "binary leaf outerplanar" in this class), network #8 (deduced from the inclusion of "binary leaf outerplanar" in this class), network #4 (deduced from the inclusion of "binary leaf outerplanar" in this class), network #16 (deduced from the inclusion of "binary leaf outerplanar" in this class)

Not in this class

Proved directly:
network #7 : Suppose by contradiction that there exists an order where there is exactly one interval for each cluster. Clusters {2,3} of vertex c and {3,4} of vertex f force 3 to be between 2 and 4 in this order. So 1 cannot be between 2 and 3 nor between 4 and 3. Therefore, either cluster {1,2,3} of vertex a and {1,3,4} of vertex e have to appear as 2 intervals in this order (split respectively by 4 or by 2).
network #3 : Suppose there exists an order of the leaves which corresponds to spread 1. Vertices b, e, g, i are all above leaf 2 as well as above another leaf which is not below the other ones. So whatever two leaves, say 1 and 3, we choose to be around leaf 2 in the order, 4 and 5 will not be, so the leaves below g and h will not be an interval in this order.

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