# ISIPhyNC - Class: binary distinct-cluster

## Definition

A phylogenetic network is binary distinct-cluster if it is binary and it is decontracted-distinct-cluster. [reference]

Bibliographic references on the Who is who in phylogenetic networks

## Relationships with other phylogenetic network classes

### Maximum subclasses

• binary regular (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.)

### Minimum superclasses

• binary FU-stable (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.)

## 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(n4) 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

## 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 : All vertices correspond to distinct clusters if hybrid vertices are contracted with their tree vertex child: c(1)={1}, c(2 contracted with c)={2}, c(3 contracted with d)={3}, c(4)={4}, c(r)={1,2,3,4}, c(a)={1,2,3}, c(b)={2,3}, c(e)={2,3,4}, c(f)={3,4}.

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 #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 #15 (deduced from the inclusion of "binary normal" in this class)

### Not in this class

Proved directly:
network #5 : Vertices r and a both have the same cluster : {1,2,3}.
network #6 : Vertices r and a both have the same cluster: {1,2,3}
network #11 : Vertices a and f both correspond to cluster {1,2}.
network #1 : Vertices e and f both correspond to cluster {1,2}.
network #4 : Vertices h and i both have the same cluster: {3,4}

Deduced from class inclusions: 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 #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")

This website was programmed and is maintained by Philippe Gambette. It was started during the internship of Maxime Morgado at LIGM, in June-July 2015, and also contains contributions made from Narges Tavassoli from November 2016 to January 2017.