ISIPhyNC - Class: binary spread-2

Definition

Relationships with other phylogenetic network classes

Maximum subclasses

• binary level-2 [reference] (The inclusion of level-2 inside spread-3 was given in this reference)
• binary spread-1

Minimum superclasses

• binary spread-3

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

• Tree Containment, negative result on binary spread-1: NP-complete, by a reduction from the general TreeContainment problem [reference]

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 #7 : Any set on any order on 4 vertices is composed of at most 2 intervals.
network #3 : Consider the order 1 2 3 4 5 of the leaves to obtain spread 2.

Deduced from class inclusions: network #5 (deduced from the inclusion of "binary unicyclic" in this class), network #12 (deduced from the inclusion of "binary level-2" in this class), network #14 (deduced from the inclusion of "binary level-2" 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 leaf outerplanar" in this class), network #9 (deduced from the inclusion of "binary spread-1" in this class), network #7 (deduced from the inclusion of "binary level-2" in this class), network #13 (deduced from the inclusion of "binary level-2" 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 level-2" in this class), network #16 (deduced from the inclusion of "binary leaf outerplanar" 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