---
abstract: 'Rooted phylogenetic networks are often used to represent conflicting phylogenetic signals. Given a set of clusters, a network is said to represent these clusters in the *softwired* sense if, for each cluster in the input set, at least one tree embedded in the network contains that cluster. Motivated by parsimony we might wish to construct such a network using as few reticulations as possible, or minimizing the *level* of the network, i.e. the maximum number of reticulations used in any “tangled” region of the network. Although these are NP-hard problems, here we prove that, for every fixed $k \geq 0$, it is polynomial-time solvable to construct a phylogenetic network with level equal to $k$ representing a cluster set, or to determine that no such network exists. However, this algorithm does not lend itself to a practical implementation. We also prove that the comparatively efficient <span style="font-variant:small-caps;">Cass</span> algorithm correctly solves this problem (and also minimizes the reticulation number) when input clusters are obtained from two not necessarily binary gene trees on the same set of taxa but does not always minimize level for general cluster sets. Finally, we describe a new algorithm which generates in polynomial-time all binary phylogenetic networks with exactly $r$ reticulations representing a set of input clusters (for every fixed $r \geq  0$).'
author:
- 'Steven Kelk[^1], Celine Scornavacca, Leo van Iersel[^2]'
bibliography:
- 'elusive\_arxiv.bib'
title: On the elusiveness of clusters
---

Introduction {#sec:introall}
============

Preliminaries {#sec:prelim}
=============

Consider a set $\mathcal{X}$ of taxa. A *rooted phylogenetic network* (on $\mathcal{X}$), henceforth *network*, is a directed acyclic graph with a single node with indegree zero (the *root*), no nodes with both indegree and outdegree equal to 1, and leaves bijectively labeled by $\mathcal{X}$. In this article we identify the leaves with ${{\mathcal X}}$. The indegree of a node $v$ is denoted $\delta^-(v)$ and $v$ is called a *reticulation* if $\delta^-(v)\geq 2$. An edge $(u,v)$ is called a *reticulation edge* if its target node $v$ is a reticulation and is called a *tree edge* otherwise. When counting reticulations in a network, we count reticulations with more than two incoming edges more than once because, biologically, these reticulations represent several reticulate evolutionary events. Therefore, we formally define the *reticulation number* of a network $N=(V,E)$ as $$r(N) = \sum_{\substack{v\in V: \delta^-(v)>0}}(\delta^-(v)-1) = |E| - |V| + 1 \enspace.$$

A *rooted phylogenetic tree* on $\mathcal{X}$, henceforth *tree*, is simply a network that has reticulation number zero. We say that a network $N$ on $\mathcal{X}$ *displays* a tree $T$ if $T$ can be obtained from $N$ by performing a series of node and edge deletions and eventually by suppressing nodes with both indegree and outdegree equal to 1. We assume without loss of generality that each reticulation has outdegree at least one. Consequently, each leaf has indegree one. We say that a network is *binary* if every reticulation node has indegree 2 and outdegree 1 and every tree node that is not a leaf has outdegree 2. Proper subsets of $\mathcal{X}$ are called *clusters*, and a cluster $C$ is a *singleton* if $|C|=1$. We say that an edge $(u,v)$ of a tree *represents* a cluster $C \subset {{\mathcal X}}$ if $C$ is the set of leaf descendants of $v$. A tree $T$ represents a cluster $C$ if it contains an edge that represents $C$. It is well-known that the set of clusters represented by a tree is a laminar set, and uniquely defines that tree. We say that a network $N$ represents a cluster $C \subset \mathcal{X}$ “in the hardwired sense” if there exists a tree edge $(u,v)$ of $N$ such that $C$ is the set of leaf descendants of $v$. Alternatively, we say that $N$ represents $C$ “in the softwired sense” if $N$ displays some tree $T$ on ${{\mathcal X}}$ such that $T$ represents $C$. In this article we only consider the softwired notion of cluster representation and henceforth assume this implicitly. A network represents a set of clusters $\mathcal{C}$ if it represents every cluster in $\mathcal{C}$ (and possibly more). The set of softwired clusters of a network can be obtained as follows. For a network $N$, we say that a *switching* of $N$ is obtained by, for each reticulation node, deleting all but one of its incoming edges. Given a network $N$ and a switching $T_N$ of $N$, we say that an edge $(u,v)$ of $N$ represents a cluster $C$ w.r.t. $T_N$ if $(u,v)$ is an edge of $T_N$ and $C$ is the set of leaf descendants of $v$ in $T_N$. The set of softwired clusters of $N$ is the set of clusters represented by all edges of $N$ w.r.t. $T_N$, where $T_N$ ranges over all possible switchings [@HusonRuppScornavacca10]. It is also natural to define that an edge $(u,v)$ of $N$ represents a cluster $C$ if there exists some switching $T_N$ of $N$ such that $(u,v)$ represents $C$ w.r.t $T_N$. Note that, in general, an edge of $N$ might represent multiple clusters, and a cluster might be represented by multiple edges of $N$.

Given a set of clusters ${{\mathcal C}}$ on ${{\mathcal X}}$, throughout the article we assume that, for any taxon $x \in {{\mathcal X}}$, ${{\mathcal C}}$ contains at least one cluster $C$ containing $x$. For a set $\mathcal{C}$ of clusters on $\mathcal{X}$ we define $r(\mathcal{C})$ as $\min \{ r(N) | N \text{ represents } \mathcal{C} \}$, we sometimes refer to this as the *reticulation number* of $\mathcal{C}$. The related concept of [*level*]{} requires some more background. A directed acyclic graph is *connected* (also called “weakly connected”) if there is an undirected path (ignoring edge orientations) between each pair of nodes. A node (edge) of a directed graph is called a *cut-node* (*cut-edge*) if its removal disconnects the graph. A directed graph is *biconnected* if it contains no cut-nodes. A biconnected subgraph $B$ of a directed graph $G$ is said to be a *biconnected component* if there is no biconnected subgraph $B' \neq 
B$ of $G$ that contains $B$. A phylogenetic network is said to be a *${\mbox{level-}\leq k}$ network* if each biconnected component has reticulation number less than or equal to $k$.[^3] A ${\mbox{level-}\leq k}$ network is called a *simple level-$\leq k$ network* if the removal of a cut-node or a cut-edge creates two or more connected components of which at most one is non-trivial (i.e. contains at least one edge). A (simple) level-$\leq k$ network $N$ is called a (simple) *level-$k$ network* if the maximum reticulation number among the biconnected components of $N$ is precisely $k$. For example, the network in Figure \[fig:bcc\] is a level-2 network while the one in Figure \[fig:gallednetwork\] is a simple level-4 network. Note that a tree is a level-0 network. For a set $\mathcal{C}$ of clusters on $\mathcal{X}$ we define $\ell(\mathcal{C})$, the *level* of $\mathcal{C}$, as the smallest $k \geq 0$ such that there exists a level-$k$ network that represents $\mathcal{C}$. It is immediate that for every cluster set $\mathcal{C}$ $r(\mathcal{C}) \geq \ell(\mathcal{C})$, because a level-$k$ network always contains at least one biconnected component containing $k$ reticulations.

We say that two clusters $C_1,C_2\subset\mathcal{X}$ are *compatible* if either $C_1\cap C_2=\emptyset$ or $C_1\subseteq C_2$ or $C_2\subseteq C_1$. Consider a set of clusters $\mathcal{C}$. The *incompatibility graph* $IG(\mathcal{C})$ of $\mathcal{C}$ is the undirected graph $(V,E)$ that has node set $V=\mathcal{C}$ and edge set $E=\{\{C_1,C_2\}\enspace |\enspace C_1$ $C_2$ $\mathcal{C}$}. We say that a set of taxa ${{\mathcal X}}' \subseteq\mathcal{X}$ is *separated* (by $\mathcal{C}$) if there exists a cluster $C\in\mathcal{C}$ that is incompatible with ${{\mathcal X}}'$, and *unseparated* otherwise.

We say that a set of clusters $\mathcal{C}$ on $\mathcal{X}$ is [*separating*]{} if it separates all sets of taxa ${{\mathcal X}}'$ such that ${{\mathcal X}}' \subset {{\mathcal X}}$ and $|{{\mathcal X}}'| \geq 2$. We say that a set of clusters $\mathcal{C}$ on $\mathcal{X}$ is [*tangled*]{} [@HusonRuppScornavacca10] if:

1.  $IG(\mathcal{C})$ is connected and has more than one node;

2.  every pair of taxa $x$ and $y$ in $\mathcal{X}$ is separated by $\mathcal{C}$.

Remember that here we assume that any taxon of ${{\mathcal X}}$ is contained in at least one cluster $C\in {{\mathcal C}}$. Then, it can easily be verified that, given a tangled set of clusters $\mathcal{C}$ on ${{\mathcal X}}$, $\mathcal{C}$ is separating. The incompatibility graph and the concept of tangled clusters are important because they highlight an important difference between (the computation of) $r(\mathcal{C})$ and $\ell(\mathcal{C})$. In [@cass] the authors show that, if $\ell(\mathcal{C})=k$, then a level-$k$ network that represents $\mathcal{C}$ can be constructed by combining in polynomial time simple level-$\leq k$ networks constructed independently for each connected component of $IG(\mathcal{C})$. The actual procedure is slightly more involved but it shows in any case that a polynomial-time algorithm for constructing simple level-$\leq k$ networks can easily be extended to a polynomial-time algorithm for constructing level-$\leq k$ networks. We will make use of this fact in Section \[sec:theory\].

Unfortunately, as has been observed by several authors, the same procedure does *not* necessarily lead to networks that have reticulation number $r(\mathcal{C})$. In other words, computation of $r(\mathcal{C})$ requires something more complicated than independently optimizing each connected component of $IG(\mathcal{C})$. An important special case, however, is when ${{\mathcal C}}$ is separating; in this case any network $N$ that represents $\mathcal{C}$ is simple (or can be trivially modified to become simple) and $r(\mathcal{C}) = \ell(\mathcal{C})$. We will formalize this in due course. To conclude the preliminaries we note that, throughout the article, we often write that an algorithm is “polynomial time” without formally specifying what the input size is. Unless otherwise specified the input is a set of clusters ${{\mathcal C}}$ on taxa set ${{\mathcal X}}$. It is sufficient to take $|{{\mathcal C}}| + |{{\mathcal X}}|$ as a lower bound on the size of the input. In some cases (such as Lemma \[lem:core\] in Section \[sec:theory\]) $|{{\mathcal C}}|$ is at most a constant factor larger than $|{{\mathcal X}}|$ and then it is sufficient to prove a running time polynomial in $|{{\mathcal X}}|$. In other cases a running time of the form $O( |{{\mathcal C}}|^{a}|{{\mathcal X}}|^{b} )$ is obtained, for constants $a$ and $b$, and this is clearly polynomial in $|{{\mathcal C}}| + |{{\mathcal X}}|$ because $(|{{\mathcal C}}| + |{{\mathcal X}}|)^2 \geq |{{\mathcal C}}||{{\mathcal X}}|$.

Structure of the article {#subsec:struc}
------------------------

To facilitate the mathematical exposition we build the results of this article up in a specific order, which differs from the order presented in the introduction. We begin with Section \[sec:theory\]: *A theoretical polynomial-time algorithm for constructing level-$k$ networks*, where we prove that, for every fixed $k \geq 0$, the problem of determining whether a level-$k$ network that represents ${{\mathcal C}}$ exists (and if so to construct such a network) is solvable in polynomial time. This section is, compared to the rest of the article, comparatively self-contained. In Section \[sec:stsets\]: *From theory to practice: the importance of ST-sets* we describe several fundamental properties of the ST-set, a special structure that plays a central role throughout the rest of the article. In Section \[sec:bitrees\]: *Clusters obtained from sets of *binary* trees on ${{\mathcal X}}$* we show how, given a set ${{\mathcal T}}$ of binary trees on ${{\mathcal X}}$, and for each fixed $r \geq 0$, it is possible to construct in polynomial time all binary phylogenetic networks with reticulation number $r$ that represent all the clusters in the input trees. We also describe <span style="font-variant:small-caps;">Clustistic</span>, which is our implementation of this algorithm built on top of already-existing software. In Section \[sec:wit\]: *Witnesses and a natural lower bound* we further develop the theory surrounding the ST-set, explicitly relating it to the computation of reticulation number. This is used extensively in Section \[sec:casseverything\]: *The optimality and non-optimality of <span style="font-variant:small-caps;">Cass</span>* where we give both positive and negative results for the [[<span style="font-variant:small-caps;">Cass</span>]{}]{} algorithm, and in the process develop a number of powerful generalizations of unification results from [@twotrees].

A theoretical polynomial-time algorithm for constructing level-$k$ networks {#sec:theory}
===========================================================================

In this section we prove that, for every fixed $k \geq 0$, the problem of determining whether a level-$k$ network exists that represents ${{\mathcal C}}$, and if so to construct such a network, can be solved in polynomial time.

We first require some auxiliary lemmas and definitions. The proofs are rather technical so we defer them to the appendix. For a node $v$ let ${{\mathcal X}}(v) \subseteq {{\mathcal X}}$ be the set of all taxa reachable from $v$ by directed paths. For an edge $e=(u,v)$ we define ${{\mathcal X}}(e)$ to be equal to ${{\mathcal X}}(v)$.

\[obs:nocutfreedom\] Let ${{\mathcal C}}$ be a separating set of clusters on ${{\mathcal X}}$. Let $N$ be any network that represents ${{\mathcal C}}$. Then each node of $N$ has at most one leaf child and for each cut-edge $(u,v)$ in $N$, $|{{\mathcal X}}(v)|=1$ or ${{\mathcal X}}(v)={{\mathcal X}}$.

Deferred to the appendix.

\[lem:simpleexists\] Let ${{\mathcal C}}$ be a separating set of clusters on ${{\mathcal X}}$. Let $N$ be any network that represents ${{\mathcal C}}$. Then there exists a simple network $N^{*}$ with at most one leaf-child per node such that $\ell(N^{*}) \leq \ell(N)$.

Deferred to the appendix.

Observation \[obs:nocutfreedom\] and Lemma \[lem:simpleexists\] formalize the idea that any network that represents a separating set of clusters is simple or can easily be made simple by deleting certain redundant parts of it. The following lemma shows that, in terms of minimizing reticulation number or level, we can assume without loss of generality that networks are binary.

\[lem:transfBinary\] Let $N$ be a phylogenetic network on ${{\mathcal X}}$. Then we can transform N into a binary phylogenetic network $N'$ such that $N'$ has the same reticulation number and level as $N$ and all clusters represented by $N$ are also represented by $N'$.

Deferred to the appendix.

Note that, given a simple binary network $N$, each node of $N$ has at most one leaf child. Armed with these technical results we are ready to prove the main result of this section.

\[lem:core\] Let ${{\mathcal C}}$ be separating set of clusters on ${{\mathcal X}}$. Then, for every fixed $k \geq 0$, it is possible to determine in polynomial time whether a level-$k$ network exists that represents ${{\mathcal C}}$, and if so to construct such a network.

From Lemmas \[lem:simpleexists\] and \[lem:transfBinary\] it is sufficient to focus on simple binary networks. We assume then that, for fixed $k$, there exists a binary simple level-$k$ network $N$ that represents ${{\mathcal C}}$. Let $|{{\mathcal X}}|=n$. Then ${{\mathcal C}}$ will contain at most $2^{k+1}(n-1)$ clusters, because there are at most $2^{k}$ trees displayed by a simple level-$k$ network, and each tree represents at most $2(n-1)$ clusters. Thus, for fixed $k$, the size of the input is polynomial in $n$. It follows from these observations that whether a set of clusters is represented by a given simple level-$k$ network can be checked in polynomial time.

![The single level-1 generator and the four level-2 generators. Here the sides have been labelled with capital letters.[]{data-label="fig:gen"}](./Figures/VanIersel34fig7)

![image](./Figures/exLemma1)

It is known that, if the leaves of $N$ are removed and all nodes with both indegree and outdegree equal to 1 are suppressed, the resulting structure will be a level-$k$ generator, defined in [@lev2TCBB]. See also Figure \[fig:gen\]. For fixed $k$, there are only a constant number of level-$k$ generators [@Gambette2009structure Proposition 2.5]. Recall that the *sides* of a level-$k$ generator are defined as the union of its edges and its nodes of indegree-2 and outdegree-0. For fixed $k$ the maximum number of sides ranging over all level-$k$ generators, is a constant.

For a cluster set ${{\mathcal C}}$ on ${{\mathcal X}}$, we write $x \rightarrow y$ if and only if every non-singleton cluster in ${{\mathcal C}}$ that contains $x$, also contains $y$. For example, for the cluster set of Figure \[fig:exLemma1\], we have $e \rightarrow d$ and $f \rightarrow e$.

In the remainder of the proof, we illustrate a simple algorithm for determining whether a binary simple level-$k$ network that represents ${{\mathcal C}}$ exists by attempting to reconstruct such a network. Let $g$ be the generator underlying $N$. We only require polynomially many tries to compute $g$, because there are only a constant number of generators. So assume we know $g$. For each side of $g$, we guess whether there are 0, 1, 2 or more than 2 leaves on that side. For each side containing exactly one leaf, we guess what that is. For each side $s$ of $g$ containing 2 or more leaves, we guess the leaf $s^{+}$ that is nearest to the root on that side, and the leaf $s^{-}$ that is furthest from the root on that side. For an example see Figure \[fig:exLemma1\]. Note that, since for each side we have only four options (0, 1, 2 or more than 2 leaves), and in the latter case only $s^{+}$ and $s^{-}$ have to be chosen, if follows that we have a polynomial number of guesses to try.

We will now show how to add the remaining leaves. Note that we may fail to insert all leaves in the network. This means that we made the wrong guess and that another set of guesses has to be checked. We say that a side $s$ is *lowest* if it does not yet have all its leaves, and there is no other such side $s'$ reachable from $s$. By reachable we mean that in the underlying generator $g$, there is a directed path from the head of side $s$ to the tail of side $s'$. Since $N$ is a directed acyclic graph, until all leaves in ${{\mathcal X}}$ have been added, there will always be a lowest side. For example, the side $F$ in Figure \[fig:exLemma1\](d) is lowest. The idea is to add leaves to the lowest side $s$, until all its leaves have been added. We then continue with remaining lowest sides until we have reconstructed $N$.

Given a lowest side $s$, with $s^{+}$ and $s^{-}$ fixed, it is possible to tell in polynomial time what the correct remaining leaves for $s$ are, as follows. Observe that a leaf $x$ that is on side $s$ in $N$ and which has not yet been added has the property $s^{+} \rightarrow x \rightarrow s^{-}$. Furthermore, there is at least one cluster $C \in {{\mathcal C}}$ such that $\{ x, s^{+}, s^{-} \} \cap C = \{ x, s^{-} \}$. There exists at least one such cluster because otherwise $\{ x, s^{+} \}$ would be not separated in ${{\mathcal C}}$, a contradiction since ${{\mathcal C}}$ is separating. We call such a cluster a *split cluster for side $s$*. Now, observe that for every split cluster $C$ for side $s$, and for every side $t \neq s$ that contains 2 or more leaves in $N$, either $\{t^{+}, t^{-}\} \cap C = \{t^{+}, t^{-}\}$ or $\{t^{+}, t^{-}\} \cap C = \emptyset$. This follows because the only edges in $N$ that represent $C$ lie on side $s$. If this is not the case, our set of guesses was incorrect and a new one has to be checked.

Now, consider any leaf $y$ that has not yet been added to the network. Assume that this leaf belongs to side $t$ for some $t$. We want to have a simple test to avoid wrongly placing it on side $s$, with $s\neq t$. Side $t$ will contain three or more leaves in $N$, so we can assume that $t^{+}$ and $t^{-}$ exist. If $s^{+} \rightarrow y \rightarrow s^{-}$ does not hold then it is immediately clear that $y$ cannot be put on side $s$. So assume (conversely) that this condition does hold, and for the same reason assume there is a split cluster $C$ for side $s$ that contains $y$. In other words, there is a cluster $C$ such that $\{ y, s^{+}, s^{-} \} \cap C = \{ y, 
s^{-} \}$. Since $t^{+} \rightarrow y \rightarrow t^{-}$ holds, it follows that $C$ also contains $t^{+}$ and $t^{-}$, because any cluster that contains $y$ also contains $t^{-}$, and we know that $C$ contains either both of $t^{+}$ and $t^{-}$, or neither of them. However, there is no edge in $N$ that can represent $C$: the only edges that represent $C$ lie on side $s$, but the fact that $s$ is the lowest side means that no cluster beginning on side $s$ can contain any leaves on side $t$. To summarize, we have a simple test for determining whether a leaf should be placed on side $s$. Once we have determined the set of leaves that should be placed on side $s$, it is easy to determine the correct order of those leaves by inspecting $\rightarrow $ relationships. Indeed, if $q$ and $p$ are two leaves that belong to side $s$, and $q$ is nearer to $s^{-}$ in the network we aim to reconstruct, then obviously $p \rightarrow q$. Since ${{\mathcal C}}$ is separating there will be (by separation) some cluster that contains $q$ but not $p$, so $q \not \rightarrow p$. [If all leaves can be added in such a way, we obtain a simple level-$k$ network on ${{\mathcal X}}$ and we can check in polynomial time if it represents ${{\mathcal C}}$. If it is not the case or we fail to insert at least one leaf in the network, another set of guesses can be checked until a simple level-$k$ network representing ${{\mathcal C}}$ (if any exist) is found]{}. This concludes the proof.

The following corollary follows automatically from the generality of the proof of Lemma \[lem:core\].

![image](./Figures/twotreesfig7)

Let ${{\mathcal C}}$ be a separating set of clusters on ${{\mathcal X}}$. Then, for every fixed $k \geq 0$, it is possible to construct in polynomial time *all* binary simple level-$k$ networks that represent ${{\mathcal C}}$.

Using Lemma \[lem:core\] we can prove the following result:

\[thm:core\] Let ${{\mathcal C}}$ be a (not necessarily separating) set of clusters on ${{\mathcal X}}$. Then, for every fixed $k \geq 0$, it is possible to determine in polynomial time whether a level-$k$ network exists that represents ${{\mathcal C}}$, and if so to construct such a network.

Recall that all tangled cluster sets are separating. It was shown in [@cass] that the existence of a polynomial-time algorithm for constructing a level-$\leq k$ network from a tangled cluster set, is sufficient to give a polynomial-time algorithm for constructing level-$k$ networks from general cluster sets. (Specifically, several tangled cluster sets are obtained by processing each non-trivial connected component of the incompatibility graph of the original cluster set [@cass; @HusonRuppScornavacca10]). Hence we can assume without loss of generality that ${{\mathcal C}}$ is tangled. Lemma \[lem:core\] is thus sufficient, and we are done.

Rooted triplets
---------------

It is interesting to note that the proof technique used in Lemma \[lem:core\] leads to a simplified proof, presented in the following corollary, of a complexity result that was first proven in [@simplicityAlgorithmica]. (The algorithm in [@simplicityAlgorithmica] yielded a much faster running time, however). Let us first recall several definitions related to rooted triplets. A *(rooted) triplet* on ${{\mathcal X}}$ is a binary phylogenetic tree on a size-3 subset of ${{\mathcal X}}$. We use $xy|z$ to denote the triplet with taxa $x,y$ on one side of the root and $z$ on the other side of the root. For triplets, the notion of “represent” can be formalized by the notion of “display” introduced above. However, for triplets “consistent with” is often used instead of “displayed by”. A triplet $xy|z$ is *consistent* with a phylogenetic network $N$ (and $N$ is *consistent* with $xy|z$) if $xy|z$ is displayed by $N$. See Figure \[fig:treestripletsclusters\] for an example. Given a phylogenetic tree $T$ on ${{\mathcal X}}$, we let  $Tr(T)$ denote the set of all rooted triplets on ${{\mathcal X}}$ that are consistent with $T$. For a set of phylogenetic trees $\mathcal{T}$, we let $Tr(\mathcal{T})$ denote the set of all rooted triplets that are consistent with some tree in $\mathcal{T}$, i.e. $Tr
(\mathcal{T})=\bigcup_{T\in\mathcal{T}}
Tr
(T)$. A set of triplets on ${{\mathcal X}}$ is *dense* if, for every size-3 subset $\{x,y,z\} \subseteq {{\mathcal X}}$, at least one of $xy|z$, $xz|y$, $yz|x$ is in the triplet set.

Let $R$ be a dense set of triplets on ${{\mathcal X}}$. Then, for every fixed $k \geq 0$, it is possible to determine in polynomial time whether a binary simple level-$k$ network exists that is consistent with $R$, and if so to construct such a network.

As pointed out in [@simplicityAlgorithmica] it is possible to determine in polynomial time whether a given network is indeed consistent with a set of input triplets. Then, the proof of Lemma \[lem:core\] holds here almost entirely. The only significant difference concerns the adding of leaves to the lowest side: a not yet allocated leaf $x$ belongs on lowest side $s$ if and only if the triplet $s^{-}x|s^{+}$ is in the input.

We shall return to rooted triplets again later in the article.

From theory to practice: the importance of ST-sets {#sec:stsets}
==================================================

The algorithm described in Section \[sec:theory\] is polynomial time but only of theoretical interest because its running time is too high to be useful in practice. In the rest of this article we will focus on practical polynomial-time algorithms. In all these algorithms the ST-set, which can informally be thought of as treelike subsets of ${{\mathcal X}}$, has a central role. We begin by formally defining ST-sets and describing their basic properties. We will expand upon these basic properties in subsequent sections of the article.

Definition and basic properties of ST-sets {#subsec:stdefs}
------------------------------------------

Given a set $S\subseteq\mathcal{X}$ of taxa, we use $\mathcal{C}\setminus S$ to denote the result of removing all elements of $S$ from each cluster in $\mathcal{C}$ and we use $\mathcal{C}|S$ to denote ${\mathcal{C}\setminus (\mathcal{X}\setminus S)}$ (the restriction of $\mathcal{C}$ to $S$). We say that a set $S \subseteq \mathcal{X}$ is an *ST-set* with respect to $\mathcal{C}$, if $S$ is not separated by $\mathcal{C}$ and any two clusters $C_1,C_2\in\mathcal{C}|S$ are compatible. Note that, unlike in [@cass], we allow the possibility that $S = \emptyset$ or $S = {{\mathcal X}}$. (We say that an ST-set $S$ is *trivial* if $S= \emptyset $ or $S= {{\mathcal X}}$). An ST-set $S$ is *maximal* if there is no ST-set $T$ with $S \subset T$. Informally, the maximal ST-sets are the result of repeatedly collapsing pairs of unseparated taxa for as long as possible; we can think of them as “islands of laminarity” within the cluster set. ST-sets first explicitly appeared in [@cass] but, as we shall see in due course, they implicitly arose earlier in the *recombination network* literature. An important feature of ST-sets is that there can in general be very many of them. For example, suppose $\mathcal{C}$ contains only $|\mathcal{X}|=n$ singleton clusters; then ${{\mathcal C}}$ has $2^n$ ST-sets. However, as the following technical results show, ${{\mathcal C}}$ will have at most $n$ *maximal* ST-sets, and they will partition $\mathcal{X}$ i.e. they are mutually disjoint and entirely cover $\mathcal{X}$. Several of the proofs have been deferred to the appendix.

\[lem:stcompute\] Let $\mathcal{C}$ be a set of clusters on ${{\mathcal X}}$ and let $S_1 \neq S_2$ be two ST-sets of $\mathcal{C}$. If $S_1 \cap S_2 \neq \emptyset$ then $S_1 \cup S_2$ is an ST-set.

Deferred to the appendix.

\[cor:maxstdisjoint\] Let $\mathcal{C}$ be a set of clusters on ${{\mathcal X}}$ and let $S_1 \neq S_2$ be two maximal ST-sets of $\mathcal{C}$. Then $S_1 \cap S_2 = \emptyset$.

\[cor:mostn\] Let $\mathcal{C}$ be a set of clusters on ${{\mathcal X}}$. Then there are at most $n$ maximal ST-sets with respect to ${{\mathcal C}}$, they are uniquely defined and they partition ${{\mathcal X}}$.

The disjointness of maximal ST-sets guarantees that there at most $n$ of them. Consider the set ${{\mathcal S}}$ of all (necessarily disjoint) maximal ST-sets of ${{\mathcal X}}$. Suppose the maximal ST-sets in ${{\mathcal S}}$ do not entirely cover ${{\mathcal X}}$. Then there is some $x \in {{\mathcal X}}$ which is disjoint from all maximal ST-sets in ${{\mathcal S}}$. Let $S$ be the ST-set of largest cardinality that contains $x$; such an ST-set must exist because $\{ x \}$ is an ST-set. $S \not \in {{\mathcal S}}$ so there exists some ST-set $S'$ such that $S \subset S'$, but this contradicts the assumption on the cardinality of $S$. Hence ${{\mathcal S}}$ partitions ${{\mathcal X}}$, and by extension ${{\mathcal S}}$ is unique.

\[lem:polymax\] The maximal ST-sets of a set of clusters ${{\mathcal C}}$ on ${{\mathcal X}}$ can be computed in polynomial time.

Deferred to the appendix.

Corollary \[cor:mostn\] and Lemma \[lem:polymax\] are perhaps not so surprising, but we have nevertheless proven them rigorously to highlight the fact that *computing* maximal ST-sets is not a complexity bottleneck. In later sections we shall see that there is a link between NP-hardness and maximal ST-sets, but that the hardness lies in selecting certain maximal ST-sets with special properties, not in the computation of the maximal ST-sets *per se*.

Let $\mathcal{T}$ be a set of trees, where each $T \in \mathcal{T}$ is a tree on $\mathcal{X}$. For a tree $T$ we write $Cl(T)$ to denote the set of clusters induced by edges of $T$ i.e. $C \in Cl(T)$ if and only if some edge of $T$ represents $C$. We let $Cl(\mathcal{T}) = \cup_{T \in \mathcal{T}} Cl(T)$. Whenever we (reasonably) assume that all singleton clusters are present in the input[^4], it is easy to see that every cluster set $\mathcal{C}$ on ${{\mathcal X}}$ can be written as $Cl(\mathcal{T})$ for some $\mathcal{T}$ as follows. We take any proper coloring of $IG(\mathcal{C})$ (i.e. map the nodes of $IG({{\mathcal C}})$ to colors such that no two adjacent nodes have the same color) and use the resulting colors to partition $\mathcal{C}$. Clusters that have been colored the same are all mutually compatible, so can be represented by a single tree corresponding to that color. Finally, whenever a subset of clusters pertaining to a color does not cover all elements of $\mathcal{X}$, the missing taxa can be attached to the root. An obvious corollary of this is that the chromatic number of $IG(\mathcal{C})$ is a lower bound on the cardinality of $\mathcal{T}$.

Whenever ${{\mathcal C}}=Cl(\mathcal{T})$ there is an important relationship between the nodes and edges of trees in $\mathcal{T}$, and the (maximal) ST-sets of $\mathcal{C}$. Let $T$ be a (not necessarily binary) tree on ${{\mathcal X}}$. In Section \[sec:prelim\] we defined when an edge of a tree represents a cluster. Here we extend this definition to *nodes* of trees. We say that a node $v$ of $T$ represents $C$ if $C$ is equal to the union of the clusters represented by some (not necessarily strict) subset of its outgoing edges. Note that if an edge $(u,v)$ represents a cluster $C$ then so does $v$.

\[lem:nonbinaryunseptree\] Let ${{\mathcal T}}= \{T_1, \ldots, T_{m}\}$ be a set of trees on ${{\mathcal X}}$. Let $\emptyset \subset {{{\mathcal X}}}'
\subset {{\mathcal X}}$ be an unseparated set with respect to $Cl({{\mathcal T}})$. Then for each $T_i \in {{\mathcal T}}$ there exists an edge $e_i$ or a node $v_i$ in $T_i$ such that $e_i$ or $v_i$ represents ${{{\mathcal X}}}'$.

Consider an arbitrary tree $T_i \in {{\mathcal T}}$. Every cluster in $Cl(T_i)$ is either disjoint from ${{{\mathcal X}}}'$, a superset of it, or a subset of it, otherwise ${{{\mathcal X}}}'$ would be separated. If some edge of $T_i$ represents ${{{\mathcal X}}}'$ then we are done. Otherwise consider some node $v$ furthest from the root which represents a cluster $C$ such that ${{{\mathcal X}}'} \subset C$. Such a $v$ must exist because if necessary we can take the root as $v$. $C$ is equal to the union of the clusters represented by some subset of the edges outgoing from $v$. Each cluster represented by an outgoing edge of $v$ is either disjoint from ${{{\mathcal X}}}'$ or a subset of it, because of the assumption on the distance of $v$ from the root. For the same reason, ${{{\mathcal X}}}'$ intersects with at least two such outgoing edge clusters of $v$. But when ${{{\mathcal X}}}'$ intersects with such a cluster it must contain it entirely, so ${{{\mathcal X}}}'$ is equal to the union of some subset of the clusters represented by edges outgoing from $v$. Hence $v$ represents ${{{\mathcal X}}}'$.

The following corollary is automatic.

\[cor:unseptree\] Let ${{\mathcal T}}= \{T_1, \ldots, T_{m}\}$ be a set of binary trees on ${{\mathcal X}}$. Let $\emptyset \subset {{{\mathcal X}}}'
\subset {{\mathcal X}}$ be an unseparated set with respect to $Cl({{\mathcal T}})$. Then for each $T_i \in {{\mathcal T}}$ there exists an edge $e_i$ such that $e_i$ represents ${{{\mathcal X}}}'$.

Note that Lemma \[lem:nonbinaryunseptree\] and Corollary \[cor:unseptree\] hold in particular for (maximal) ST-sets, because all ST-sets are unseparated. Hence the two following straightforward extensions to ST-sets, which we will use extensively in the next section. Recall that an ST-set $S$ is trivial if $S=\emptyset$ or $S={{\mathcal X}}$.

\[cor:stsetbinary\] Let ${{\mathcal T}}= \{T_1, \ldots, T_{m}\}$ be a set of binary trees on ${{\mathcal X}}$. Let $S$ be a non-trivial ST-set with respect to $Cl({{\mathcal T}})$. Then for each $T_i \in {{\mathcal T}}$ there exists an edge $e_i$ in $T_i$ such that $e_i$ represents $S$.

\[cor:stedges\] Let ${{\mathcal T}}= \{T_1, \ldots, T_{m}\}$ be a set of binary trees on ${{\mathcal X}}$. Then $Cl({{\mathcal T}})$ contains at most $2(n-1)$ non-trivial ST-sets, and for every such ST-set $S$ of $Cl({{\mathcal T}})$ and every tree $T_i \in {{\mathcal T}}$ there exists a unique edge $e_i$ of $T_i$ such that ${{\mathcal X}}(e_i)=S$ and such that the subtree rooted at the head of $e_i$ is the unique tree that represents exactly the cluster set $Cl({{\mathcal T}})|S$.

Given any tree $T_i  \in {{\mathcal T}}$, $Cl(T_i)$ will contain exactly $2(n-1)$ edges and consequently $2(n-1)$ clusters. Since an ST-set is by definition unseparated, each ST-set of $Cl({{\mathcal T}})$ is a subset of the cluster set $Cl(T_i)$ (for any $i$) and there are thus at most $2(n-1)$ ST-sets. Moreover, by definition, for any ST-set $S$ of $Cl({{\mathcal T}})$ we have that the set $Cl({{\mathcal T}})|S$ is compatible. Since two non-isomorphic binary trees on the same taxa set induce at least two incompatible clusters, this concludes the proof.

Informally Corollary \[cor:stedges\] states that when ${{\mathcal T}}$ consists solely of binary trees, each non-trivial ST-set corresponds to some subtree that is common to all trees in ${{\mathcal T}}$.

Clusters obtained from sets of *binary* trees on ${{\mathcal X}}$ {#sec:bitrees}
=================================================================

Let ${{\mathcal T}}$ be a set of binary trees on ${{\mathcal X}}$. In this section we prove prove that, for fixed $r \geq 0$, it is possible to construct in polynomial time all binary phylogenetic networks with reticulation number $r$ that represent $Cl({{\mathcal T}})$. We also describe our new program <span style="font-variant:small-caps;">Clustistic</span> which implements this algorithm. <span style="font-variant:small-caps;">Clustistic</span> is in itself an important “proof of concept”: it has been rapidly prototyped by, building on insights from [@twotrees], slightly modifying existing software that was originally conceived to reconstruct binary level-$k$ networks not from clusters but rooted triplets.

Let $N$ be a network on ${{\mathcal X}}$ and let $T'$ be some tree on ${{\mathcal X}}' \subset {{\mathcal X}}$. We say that $T'$ is a *Subtree Below a Reticulation* (SBR) of $N$ if there is a reticulation node $v$ in $N$ such that no reticulation nodes $v' \neq v$ are reachable from $v$ by a directed path, and that the subnetwork rooted at $v$ (or, when $v$ has outdegree exactly 1, the child of $v$) is exactly equal to $T'$. It is easy to show that (by virtue of its acyclicity) every network contains at least one SBR [@simplicityAlgorithmica]. A simple though critical observation is:

\[obs:SBR\_ST\] If $T'$ is an SBR of a network $N$ on ${{\mathcal X}}$ that represents a cluster set ${{\mathcal C}}$, and $T'$ has taxa set ${{\mathcal X}}'$, then ${{\mathcal X}}'$ is an ST-set with respect to ${{\mathcal C}}$.

We will make repeated use of this throughout the rest of the article. (Note however that in general an ST-set will not specify a unique SBR).

Given a network $N$ with an SBR $T$ we denote by $N\setminus_{T}$ the network obtained from $N$ by deleting $T$ and for as long as necessary applying the following tidying-up operations until they are no longer needed: deleting any node with outdegree zero that is not labelled by an element of ${{\mathcal X}}$; suppressing all nodes with indegree and outdegree both equal to 1; replacing multi-edges with single edges; deleting nodes with indegree-0 and outdegree-1.

We call $(S_1, S_2, ..., S_p)$ $(p \geq 0)$ a *(maximal) ST-set sequence of ${{\mathcal C}}$* if $S_1$ is a (maximal) ST-set of ${{\mathcal C}}$, $S_2$ is a (maximal) ST-set of ${{\mathcal C}}\setminus S_1$, $S_3$ is a (maximal) ST-set of ${{\mathcal C}}\setminus S_1 \setminus S_2$ and so on. Such a sequence is additionally a *tree* sequence if all the clusters in ${{\mathcal C}}\setminus S_1 \setminus \ldots \setminus S_p$ are mutually compatible i.e. can be represented by a tree. We denote by $p$ be the *length* of the sequence; $p=0$ denotes the empty tree sequence.

\[lem:treeseq\] Let $N$ be a network that represents some cluster set ${{\mathcal C}}$ on ${{\mathcal X}}$. Then there exists a sequence of SBRs that need to be removed to prune $N$ into a tree, and this corresponds to an ST-set tree sequence of ${{\mathcal C}}$ of length $r(N)$.

If $N$ is a tree then there is an empty tree sequence. Otherwise, $N$ has an SBR $T'$ with taxa set ${{\mathcal X}}'$ and the network $N\setminus_{T'}$ represents the cluster set ${{\mathcal C}}\setminus {{\mathcal X}}'$. Clearly $r(N') < r(N)$. By observation \[obs:SBR\_ST\], we let $S_1$ equal ${{\mathcal X}}'$ and $d = r(N)-r(N')$. If $d>1$ then we let $S_2, \ldots, S_d$ all equal $\emptyset$, the empty ST-set. We use these empty ST-sets to model the situation when removing the SBR would cause multiple reticulation nodes to disappear simultaneously. Now, $N'$ also has at least one SBR, so we can iterate the whole process. We can repeat this until we obtain a tree: at this point we will have an ST-set tree sequence of length exactly $r(N)$.

In the following observation we make use of the fact that the operation $N \setminus_{T}$ is also meaningfully defined when the tree $T$ is exactly the subtree rooted at some node of $N$.

\[obs:staysbinary\] Let ${{\mathcal T}}= \{T_1, \ldots, T_{m}\}$ be a set of binary trees on ${{\mathcal X}}$. Let $S$ be a non-trivial ST-set of $Cl({{\mathcal T}})$. Then $Cl({{\mathcal T}})\setminus S = Cl({{\mathcal T}}')$ where ${{\mathcal T}}'$ is a set of at most $m$ binary trees $\{T'_1, \ldots, T'_{m}\}$ on ${{\mathcal X}}\setminus S$ with $T'_i= T_i\setminus T_v$, where $e_i = (u,v)$ is the edge of $T_i$ that represents $S$ (which exists by Corollary \[cor:stedges\]) and $T_v$ is the subtree rooted at $v$.

![Let ${{\mathcal C}}$ be some set of clusters represented by the network on the right. If we guess that ST-set $S=\{h,i,j\}$ corresponds to an SBR and remove it, we obtain the tree on the left. To reverse the process we add (a tree corresponding to) $S$ below a reticulation node whose incoming edges subdivide edges $x$ and $y$. []{data-label="fig:hangback"}](./Figures/hangBack)

[c]{}

  --------------------------------- -- --------------------------------------------- -- ------------------------------------------
   ![image](./Figures/hanging.pdf)      ![image](./Figures/hangingOneEdgeTwice.pdf)      ![image](./Figures/hangingMultiedge.pdf)
                 (a)                                        (b)                                            (c)
  --------------------------------- -- --------------------------------------------- -- ------------------------------------------

\[thm:allbinary\] Let ${{\mathcal T}}= \{T_1, \ldots, T_{m}\}$ be a set of binary trees on ${{\mathcal X}}$. Then for a constant $r \geq 0$ it is possible to construct in polynomial time *all* binary networks with reticulation number at most $r$ that represent $Cl({{\mathcal T}})$ (if any exist).

Without loss of generality assume we wish to construct all such networks with reticulation number *exactly* $r$. Let us suppose that at least one such network $N$ exists. By Lemma \[lem:treeseq\] there is an ST-set tree sequence ${{\mathcal S}}= (S_1, \ldots, S_{r})$ for $Cl({{\mathcal T}})$ and this corresponds to a sequence of SBRs that, when removed, will prune $N$ into a tree. Let $|X|=n$. Now, note that by Observation \[obs:staysbinary\] and Corollary \[cor:stedges\] there are at most $O( n^{r} )$ ST-set tree sequences, which is polynomial in $n$ for fixed constant $r$. ${{\mathcal S}}$ will be one of these, so we can find ${{\mathcal S}}$ in polynomial time. It remains to show how, assuming we have found ${{\mathcal S}}$, we can reconstruct $N$. First, note that for a binary tree $T$ on ${{\mathcal X}}$, $T$ is the *unique* tree on ${{\mathcal X}}$ that represents $Cl(T)$. The clusters that still remain after removing $S_r$ can be represented by a tree, and in particular (by Observation \[obs:staysbinary\]) by a unique binary tree. We call this tree $N_r$. We want to obtain $N_{r-1}$ by inserting (a tree corresponding to) $S_{r}$ into $N_{r}$. In particular, we wish to introduce a new reticulation node into $N_r$ below which a tree $T$ (itself binary and unique by Corollary \[cor:stedges\]) that represents $S_r$ will be attached. We have two possibilities to do this: we subdivide two (not necessarily distinct) edges and use these as the tails of the new reticulation edges, see Figures \[fig:hangtypes\](a) and (b), or we subdivide one edge *once* and use two *identical* reticulation edges, see Figure \[fig:hangtypes\](c). Note that, if we only subdivide one edge once, we actually create a multi-edge and by our definition of phylogenetic network such edges are not allowed. However it might be necessary to create such multi-edges during *intermediate* iterations to ensure that all phylogenetic networks, including “redundant” ones, are constructed.

Unfortunately we do not know in general which edge(s) of $N_{r}$ to subdivide to create the new connection point(s). However, there are only polynomially many edges in $N_r$, so we simply try them all. Then we repeat the process, inserting $S_{r-1}$ into $N_{r-1}$ to obtain $N_{r-2}$, and so on until we have obtained $N_0$. Given that $r$ is a constant we can test in polynomial time whether $N_0$ represents all the clusters in ${{\mathcal C}}$ (see proof of Lemma \[lem:core\]).

Just as in the similar algorithm described in [@simplicityAlgorithmica] there are several slight technicalities that should be noted. Whenever some $S_i = \emptyset$ we use a “dummy” taxon (i.e. some taxon not in ${{\mathcal X}}$) as the tree that we attach below a reticulation. The function of this is to ensure that subsequent iterations can subdivide the edge leaving the reticulation i.e. it is a placeholder. (This will be necessary when the removal of a single SBR caused the disappearance of two or more reticulations). These dummy taxa can be removed just before $N_0$ is inspected to check whether it represents ${{\mathcal C}}$. Any $N_0$ that at this point still contains a dummy taxon whose parent is a reticulation, should be rejected, because it means at least one reticulation was not used. Secondly, when we construct the tree $N_r$ we actually add a “dummy root” which is simply a new node $\rho'$ and a single edge from $(\rho', \rho)$ where $\rho$ is the root of $N_r$. This deals with the situation when the removal of some SBR caused the current root to disappear and a new root to take its place. At the end, $\rho'$ and the edge leaving it should be removed. Finally, note that any multi-edges created by intermediate iterations of the algorithm should all have disappeared (i.e. have been subdivided by reticulation edges) by the time $N_0$ has been reached; for this reason we reject any $N_0$ that still contains multi-edges.

The network $N$ we would like to reconstruct will eventually be found as some $N_0$, and given that we made no assumptions about $N$ this shows that the algorithm constructs all possible $N$.

\[thm:allsimple\] Let ${{\mathcal T}}= \{T_1, \ldots, T_{m}\}$ be a set of binary trees on ${{\mathcal X}}$. Then for a constant $k \geq 0$ it is possible to construct in polynomial time *all* binary simple level-$\leq k$ networks that represent $Cl({{\mathcal T}})$ (if any exist).

For each network produced by the algorithm described in Theorem \[thm:allbinary\] we can easily check in polynomial time whether it is biconnected.

It is worth noting at this stage an important link with the rooted triplet literature. Recall the following proposition and lemma from [@twotrees], an article in which the relationship between trees, clusters and triplets was discussed more broadly. Proposition \[prop:clustrip\] refers to not necessarily binary trees.

\[prop:clustrip\] (Van Iersel, Kelk [@twotrees]) For any set ${{\mathcal T}}$ of trees on the same set ${{\mathcal X}}$ of taxa, any phylogenetic network on ${{\mathcal X}}$ representing $Cl({{\mathcal T}})$ is consistent with $Tr({{\mathcal T}})$.

\[lem:binary2\] (Van Iersel, Kelk [@twotrees]) Let $N$ be a phylogenetic network on $\mathcal{X}$ and $\mathcal{T}$ a set of binary trees on $\mathcal{X}$. Then there exists a binary phylogenetic network $N'$ on $\mathcal{X}$ such that (a) $N'$ has the same reticulation number and level as $N$, (b) if $N$ displays all trees in $\mathcal{T}$ then so too does $N'$, (c) if $N$ is consistent with $Tr(\mathcal{T})$ then so too is $N'$ and (d) if $N$ represents $Cl(\mathcal{T})$ then so too does $N'$.

Suppose that we have an Algorithm $A$ which, for each fixed $r \geq 0$, can construct in polynomial time every binary network consistent with $Tr({{\mathcal T}})$ that has at most $r$ reticulations, where ${{\mathcal T}}$ is a set of binary trees on ${{\mathcal X}}$. Suppose $A'$ is an algorithm that examines in turn every network output by $A$ and rejects it if it does not represent $Cl({{\mathcal T}})$ (such a filtering step can be done for each network in polynomial time for fixed $r$, see proof of Lemma \[lem:core\]). If there exists a network $N$ on ${{\mathcal X}}$ with at most $r$ reticulations that represents $Cl({{\mathcal T}})$ then by Lemma \[lem:binary2\] there exists a binary network $N'$ on ${{\mathcal X}}$ with this property. Furthermore, in that case $N'$ will by Proposition \[prop:clustrip\] be consistent with $Tr({{\mathcal T}})$. The algorithm $A'$ is thus guaranteed to eventually find $N'$. The practical consequence of this is that, simply by adding a filtering step, triplet software can in some cases easily be modified to work for clusters. Indeed, they can be used to determine whether a network with $r$ reticulations that represents ${{\mathcal C}}$ exists and if so to construct all binary networks with this property. As proof of concept we have taken the triplet software <span style="font-variant:small-caps;">SIMPLISTIC</span> (based on the ideas described in [@simplicityAlgorithmica]), removed its biconnectedness-checking subroutine so that it generates all binary networks with up to $r$ reticulations (and not just all simple level-$\leq r$ binary networks), and added the cluster filtering step as described above. This whole process took only one day of programming, and lead to the new software package <span style="font-variant:small-caps;">CLUSTISTIC</span> which implements the result described in Theorem \[thm:allbinary\]. This software is available for download at <http://skelk.sdf-eu.org/clustistic>.

Witnesses and a natural lower bound {#sec:wit}
===================================

Now, let ${{\mathcal T}}= \{T_1, \ldots, T_{m}\}$ be a set of $m$ not necessarily binary trees on ${{\mathcal X}}$. Let $S$ be a non-trivial ST-set of $Cl({{\mathcal T}})$. We know by Lemma \[lem:nonbinaryunseptree\] that for each $T_i \in {{\mathcal T}}$ there is an edge $e_i$ or node $v_i$ in $T_i$ that represents $S$. We define a *witness* for $S$ in $T_i$ as follows. If $T_i$ contains an edge $e_i = (u_i,v_i)$ that represents $S$, then a witness is any leaf descendant $x_i \in {{\mathcal X}}$ of $u_i$ that does not appear in $S$, i.e. $x_i \in ({{\mathcal X}}(u_i) \setminus  S)$. Otherwise, from Lemma \[lem:nonbinaryunseptree\] there exists a node $v_i$ in $T_i$ that represents $S$, and in that case a witness is any leaf descendant $x_i \in ({{\mathcal X}}(v_i) \setminus  S)$. The only ST-sets with no witnesses are ${{\mathcal X}}$ and the empty set, hence the restriction to non-trivial ST-sets. As an example consider the four trees ${{\mathcal T}}$ in Figure \[fig:4t\]. Consider the ST-set $\{1\}$ of $Cl({{\mathcal T}})$. In the top-left tree and bottom-left tree the only possible witness for this is taxon 5. In the top-right tree the only witness is taxon 3, and in the bottom-right tree the only witness is taxon 2.

Given a set of trees ${{\mathcal T}}$ on ${{\mathcal X}}$ and a non-trivial ST-set $S$ of $ {{\mathcal X}}$, let $W \subseteq {{\mathcal X}}$ be any subset of taxa such that, for each tree $T_i \in {{\mathcal T}}$, there exists $x \in W$ that is a witness for $S$ in $T_i$. We call such a set a *witness set* of $S$ in ${{\mathcal T}}$. Clearly there exist $W$ such that $|W| \leq m$. For example, for the set of trees in Figure \[fig:4t\], $\{2,3,5\}$ is a possible witness set for $\{1\}$. The two following simple observations are critical.

\[obs:wit\] Let ${{\mathcal T}}$ be a set of trees on ${{\mathcal X}}$, $S$ a non-trivial ST-set of $ {{\mathcal X}}$ and $W$ a witness set of $S$ in ${{{\mathcal T}}}$. Then for each $C \in {{\mathcal C}}({{\mathcal T}})$ such that $S \subset C$, $W \cap C \neq \emptyset$.

For each cluster $C \in {{\mathcal C}}({{\mathcal T}})$ there is at least one edge $e = (u,v)$ in some $T_i \in {{\mathcal T}}$ such that $e$ represents $C$. Let $e_i$ $(v_i)$ be the edge (node) in $T_i$ that represents $S$. Given that $S \subset C$, all leaf descendants of $v$ must also include all leaf descendants of the tail of $e_i$ $(v_i)$. In particular, all possible witnesses for $S$ in $T_i$.

To understand the meaning of Observation \[obs:wit\] it is helpful to again consider the example of ST-set $\{1\}$ in the context of Figure \[fig:4t\]. We see that any cluster that is a strict superset of $\{1\}$ must contain at least one of the taxa from $\{2,3,5\}$.

\[obs:wit2\] Let ${{\mathcal T}}= \{T_1, \ldots, T_{m}\}$ be a set of trees on ${{\mathcal X}}$ such that $m \geq 2$ and let $S$ be a non-trivial ST-set of ${{\mathcal C}}$. Let $W$ be a smallest-cardinality witness set of $S$ in ${{\mathcal T}}$. If $|W| = m$ then for each $C \in {{\mathcal C}}({{\mathcal T}})$ such that $S \cap C = \emptyset$, $W \setminus C \neq \emptyset$.

Note that it is not possible for a witness for $S$ in a tree $T_i \in {{\mathcal T}}$ to also be a witness for $S$ in $T_j \neq T_i$, because then $|W| \leq m-1$. So each witness in $W$ comes from a different tree in ${{\mathcal T}}$. Suppose then that there is some $C\in {{\mathcal C}}({{\mathcal T}})$ such that $S \cap C = \emptyset$ and $W \setminus C = \emptyset$. Clearly, since $W\neq \emptyset$, $W \subseteq C$, and $|C| \geq |W| \geq 2$. Furthermore some edge $e_i$ in some $T_i$ represents $C$. Combining the fact that $S \cap C = \emptyset$ and $W \subseteq C$ leads us to the conclusion that all elements of $W$ are possible witnesses for $S$ in $T_i$. But then some element $x$ of $W$ is a witness for $S$ both in $T_i$ and also in some $T_j \neq T_i$, contradiction.

As mentioned in the proof of Observation \[obs:wit2\], a witness set $W$ (for a given ST-set $S$) with $m-1$ or fewer elements exists if and only if the possible witnesses for $S$ ranging across the different $T_i$ are not all mutually disjoint. If a witness set with $m-1$ or fewer elements does not exist then in the following results any witness set with $m$ elements will turn out to be sufficient, as a consequence of Observation \[obs:wit2\]. This will become clear in due course.

A natural lower bound on $r({{\mathcal T}})$ that is tight for clusters obtained from two (not necessarily binary) trees\[sec:MSTlowerbound\]
---------------------------------------------------------------------------------------------------------------------------------------------

\[lem:lowerbound2\] Given a set of clusters ${{\mathcal C}}$ on ${{\mathcal X}}$, there exists a maximal ST-set tree sequence $(S_1, S_2, ..., S_p)$ such that ${p} \leq r({{\mathcal C}})$.

The proof is equivalent to that of Lemma \[lem:treeseq\] but for the fact that no empty ST-set is inserted in the maximal ST-set tree sequence.

We define the *maximal ST-set lower bound for ${{\mathcal C}}$* (MST lower bound for short) as the cardinality of the smallest maximal ST-set tree sequence for ${{\mathcal C}}$. By Lemma \[lem:lowerbound2\] this is a genuine lower bound on $r({{\mathcal C}})$. In general it is however a rather weak lower-bound: consider the set ${{\mathcal C}}^{i}$ of clusters on $X^{i} = \{r, x_1, \ldots x_i\}$ defined by $\{ \{r,x_j\} | 1 \leq j \leq i \}$. The MST lower bound for this cluster set is always 1, while $r({{\mathcal C}}^{i})$ rises linearly in $i$. However, as we shall see the tightness of the bound is to some extent correlated with the number of trees which generate the clusters, with two trees being a special case. We first require some definitions and auxiliary lemmas.

Consider a network $N$ on ${{\mathcal X}}$. Let $\mathcal{X'} = \{\rho \} \cup {{\mathcal X}}$ where $\rho \not \in {{\mathcal X}}$ is some arbitrary symbol representing the root of $N$. Let $T$ be some tree on ${{\mathcal X}}^{*}$ where ${{\mathcal X}}^{*} \cap {{\mathcal X}}' = \emptyset$ and let $H$ be a subset of ${{\mathcal X}}'$. We can obtain a new network $N'$ on $({{\mathcal X}}^{*} \cup {{\mathcal X}})$ *by hanging $T$ from $H$ in $N$*. Informally $N'$ is obtained by hanging the tree $T$ beneath a new reticulation which has $|H|$ incoming edges, where each such incoming edge begins “just above” an element of $H$. Formally the transformation is as follows. First we add a new edge $(r,r')$ to $T$, where $r'$ is the root of $T$ and $r$ is a new node. For each $h \in H \setminus \{\rho\}$ we then subdivide the unique edge entering $h$; let $h_p$ be the new parent (with indegree and outdegree 1) of $h$. For each $h \in H \setminus \{\rho\}$ we then add a new edge $(h_p,r)$. Finally, if $\rho \in H$ we also add an edge from the root of $N$ to $r$; we call this a *root edge*. It is clear that $r(N') = r(N) + |H|-1$.

\[lem:hangback\] Let ${{\mathcal T}}= \{T_1, \ldots, T_{m}\}$ be a set of $m$ trees on ${{\mathcal X}}$ and let ${{\mathcal C}}= Cl({{\mathcal T}})$. Let $S$ be a maximum ST-set of ${{\mathcal C}}$. Let $N$ be any network on ${{\mathcal X}}\setminus S$ that represents ${{\mathcal C}}\setminus S$. Then it is possible to extend $N$ to obtain a new network $N'$ that represents ${{\mathcal C}}$ such that $r(N') \leq r(N) + (m-1)$.

Let $T_{S}$ be the unique tree on taxa set $S$ such that ${{\mathcal C}}(T_S)= {{\mathcal C}}| S$. Let $W$ be a minimum-cardinality witness set for $S$ in ${{\mathcal T}}$. Clearly $1 \leq |W| \leq m$. If $|W|=m$ then we let $N'$ be the network obtained by hanging $T_{S}$ from $W$ in $N$. If $|W| < m$ then we let $N'$ be the network obtained by hanging $T_{S}$ from $W \cup \{ \rho \}$ in $N$. Clearly, $r(N') \leq r(N) + (m-1)$. It remains only to show that $N'$ represents ${{\mathcal C}}$. Consider any cluster $C \in {{\mathcal C}}$. There are three cases to consider. (1) If $C \subseteq S$ then $N'$ clearly represents $C$ because $T_S$ already represented ${{\mathcal C}}|S$. (2) If $S \subset C$ then consider $C' = C \setminus S$. Clearly $N$ represents $C'$. By Observation \[obs:wit\] there exists some $w \in W \cap C$. Since $W \cap S= \emptyset$, this implies that there exists some $w \in W \cap C'$.

To see that $N'$ represents $C$ consider any tree displayed by $N$ that represents $C'$. We can extend this tree by “switching on” the new reticulation edge that begins above $w$, i.e. the edge $(w_p,r)$, and “switching off” the remaining reticulation edges. (3) If $S \cap C = \emptyset$ then there are two subcases. (3.1) If $|W| < m$ then we can “switch on” the root edge that enters the reticulation above $T_S$, i.e. the edge $(\rho,r)$, and “switch off” all other reticulation edges entering $T_S$. (3.2) If $|W|=m$ then by Observation \[obs:wit2\] there exists $w \in W \setminus C$. In $N'$ we can thus “switch on” the new reticulation edge that begins above $w$, and “switch off” the rest.

\[thm:tightbound\] Let ${{\mathcal T}}= \{T_1, \ldots, T_{m}\}$ be a set of $m$ trees on ${{\mathcal X}}$ and let ${{\mathcal C}}= Cl({{\mathcal T}})$. Let $p$ be the MST lower bound for ${{\mathcal C}}$. Then $r({{\mathcal C}}) \leq (m-1)p$.

Given a tree $T$ and a node $u$ of $T$, we denote by ${{\mathcal X}}(T)$ the label set of $T$ and by $T_u$ the subtree rooted at $u$. From Lemma \[lem:lowerbound2\] we already know that $p \leq r({{\mathcal C}})$. Now, let $(S_1, S_2, ..., S_p)$ be a maximal ST-set tree sequence for ${{\mathcal C}}$. We will complete the proof by showing how to explicitly construct a network $N$ with reticulation number at most $(m-1)p$ that represents ${{\mathcal C}}$. We define ${{\mathcal C}}_{i}$, $1 \leq i \leq p$, as ${{\mathcal C}}\setminus S_1 \setminus \ldots \setminus S_{i}$ and ${{\mathcal C}}_{0}$ as ${{\mathcal C}}$. By Lemma \[lem:nonbinaryunseptree\] it can be seen that for each $i$, ${{\mathcal C}}_{i} = Cl( {{\mathcal T}}_{i} )$ where ${{\mathcal T}}_{i}$ is a set of at most $m$ trees on ${{\mathcal X}}\setminus S_1 \setminus \ldots \setminus S_{i}$ and where ${{\mathcal T}}_{0} = {{\mathcal T}}$. In particular, ${{\mathcal T}}_{i+1}$ can be obtained from ${{\mathcal T}}_{i}$ as follows. Given a tree $T_j$ in ${{\mathcal T}}_{i}$, let (without loss of generality) $u_j$ be the node of $T_j$ such that $S_i$ is equal to the union of the clusters represented by some not necessarily strict subset of its outgoing edges. Such a $u_j$ exists by Lemma \[lem:nonbinaryunseptree\]. Let $Q = \{v_1, \ldots, v_k\}$ be the set of children of $u_j$ such that for each $v \in Q$, ${{\mathcal X}}(T_{v})$ contains at least one element of $S_{i}$. The set of trees ${{\mathcal T}}_{i+1}$ can be obtained from ${{\mathcal T}}_{i}$ by computing, for each tree $T_j$ in ${{\mathcal T}}_{i}$ the tree $T_j \setminus {T_{v_1}} \ldots \setminus {T_{v_k}}$ i.e. pruning away the subtrees corresponding to $S_i$ and tidying up the resulting tree.

Now, consider ${{\mathcal C}}_{p}$. Let $N_{p}$ be the unique tree such that ${{\mathcal C}}(N_p)= {{\mathcal C}}_{p}$; $N_p$ will be equal to the single tree in ${{\mathcal T}}_{p}$. By Lemma \[lem:hangback\] we can obtain a network $N_{p-1}$ with $(m-1)$ reticulations that represents ${{\mathcal C}}_{p-1}$ by taking ${{\mathcal T}}= {{\mathcal T}}_{p-1}$, $N = N_{p}$ and $S = S_{p}$ in the proof of that lemma. We iterate this process for $p-2, p-3, \ldots 1$. This lasts at most $p$ iterations in total, and each iteration adds $(m-1)$ to the reticulation number, thus yielding a network $N_{0}$ that represents ${{\mathcal C}}$ with reticulation number (at most) $(m-1)p$.

\[cor:tightbound\] Let ${{\mathcal T}}= \{T_1, T_{2}\}$ be a set of two not necessarily binary trees on ${{\mathcal X}}$ and let ${{\mathcal C}}= Cl({{\mathcal T}})$. Let $p$ be the MST lower bound for ${{\mathcal C}}$. Then $r({{\mathcal C}}) = p$.

In [@twotrees] it is shown that it is NP-hard and APX-hard to compute $r({{\mathcal C}})$ where ${{\mathcal C}}$ is the set of clusters obtained from two binary trees on ${{\mathcal X}}$. The following corollary is thus immediate.

\[cor:boundishard\] The computation of the MST lower bound is NP-hard and APX-hard.

It is interesting to note that Lemma \[lem:lowerbound2\] and Corollary \[cor:boundishard\] have, in some sense, already appeared in the phylogenetic network literature, albeit in the language of *recombination networks*. Specifically, in [@twotrees] we highlight that the phylogenetic network model described there (and also used here) is in a strong sense identical to the recombination network model under the assumption of an all-0 root, the infinite sites model and multiple crossover recombination. The computational lower bound described in Algorithm 3 of [@myers2003] is, taking this equivalence into account, essentially identical to the MST lower bound. In [@bafnabansal2006] it is shown that computing this bound is NP-hard, by reduction from <span style="font-variant:small-caps;">MAX-2-SAT</span>. The same authors also give an exponential-time dynamic programming algorithm for computing the bound because in [@myers2003] it was not explicitly indicated how this should be computed.

The optimality and non-optimality of <span style="font-variant:small-caps;">Cass</span> {#sec:casseverything}
=======================================================================================

The [[<span style="font-variant:small-caps;">Cass</span>]{}]{} algorithm for constructing simple level-$k$ networks was presented in [@cass]. The algorithm was designed to produce solutions of minimum level, not of minimum reticulation number. However, when the input is a separating set ${{\mathcal C}}$ of clusters on ${{\mathcal X}}$, minimizing the level or the reticulation number is equivalent. Indeed, such cluster sets have the property that any network that represents them is simple or can easily be made simple (see Lemma \[lem:simpleexists\]) and a simple network contains exactly one non-trivial biconnected component.

The [[<span style="font-variant:small-caps;">Cass</span>]{}]{} algorithm can be used as a subroutine in a divide and conquer algorithm to construct general level-$k$ networks. We will call this more general algorithm [[<span style="font-variant:small-caps;">Cass$^{\textsc{DC}}$</span>]{}]{}. The basic idea of [[<span style="font-variant:small-caps;">Cass$^{\textsc{DC}}$</span>]{}]{} is that it transforms each connected component of $IG({{\mathcal C}})$ into a tangled set of clusters, runs [[<span style="font-variant:small-caps;">Cass</span>]{}]{} separately on each of these tangled sets, and combines the resulting simple networks into a single final network $N$ (Recall that tangled cluster sets are separating). The final network $N$ has reticulation number equal to the sum of the reticulation number of the simple networks produced by [[<span style="font-variant:small-caps;">Cass</span>]{}]{}, and $N$ has level equal to the maximum level ranging over all the simple networks. For more details on the divide and conquer strategy, see [@cass] and [@HusonRuppScornavacca10], Section 8.2.

In [@cass] the authors proved that if there is a level-$\leq 2$ network that represents ${{\mathcal C}}$, then [[<span style="font-variant:small-caps;">Cass$^{\textsc{DC}}$</span>]{}]{} will find such a solution with minimal level. Here we clarify several other properties of the algorithm. On the negative side we show (using a special separating cluster set) that the [[<span style="font-variant:small-caps;">Cass</span>]{}]{} algorithm does not in general minimize level. On the positive side we show that when the input set ${{\mathcal C}}$ is equal to $Cl(\{T_1,T_2\})$ for any two (not necessarily binary) trees, [[<span style="font-variant:small-caps;">Cass$^{\textsc{DC}}$</span>]{}]{} correctly minimizes level. In fact we show something even stronger: in this case [[<span style="font-variant:small-caps;">Cass$^{\textsc{DC}}$</span>]{}]{} also correctly constructs networks with minimum reticulation number, which in turn is exactly equal to the hybridization number of the two input trees i.e. the number of reticulations required to display the trees themselves. We conclude with several open questions regarding [[<span style="font-variant:small-caps;">Cass</span>]{}]{}.

Cass: the high-level idea {#subsec:casshigh}
-------------------------

Let $N$ be a network that represents a set of clusters ${{\mathcal C}}$ on ${{\mathcal X}}$. Let $S$ be a non-trivial ST-set with respect to ${{\mathcal C}}$. We say that $S$ is *under a cut-edge* if $N$ contains a cut-edge $(u,v)$ such that the subnetwork rooted at $v$ is a tree that represents ${{\mathcal C}}|S$.

The next two results formed (implicitly) the direct inspiration for <span style="font-variant:small-caps;">Cass</span>, which was designed to be a generalization of these results.

\[lem:moveST\] Let $N$ be a network that represents a set of clusters ${{\mathcal C}}$ on ${{\mathcal X}}$. Let $S$ be a non-trivial ST-set with respect to ${{\mathcal C}}$. Then there exists a network $N'$ such that $r(N') \leq r(N)$, $\ell(N') \leq \ell(N)$, $S$ is under a cut-edge in $N'$ and for each ST-set $S'$ such that $S' \cap S = \emptyset$ and $S'$ is under a cut-edge in $N$, $S'$ is also under a cut-edge in $N'$.

Deferred to the appendix.

The following corollary follows from the fact that maximal ST-sets are disjoint:

\[cor:maxundercut\] Let $N$ be a network that represents a set of clusters ${{\mathcal C}}$. There exists a network $N'$ such that $r(N') \leq r(N)$, $\ell(N') \leq \ell(N)$ and all maximal ST-sets (with respect to ${{\mathcal C}}$) are below cut-edges.

The pseudocode for [[<span style="font-variant:small-caps;">Cass</span>]{}]{} was originally given in [@cass]. That exposition is however rather dense and technical. See Section 8.5 of [@HusonRuppScornavacca10] for a clearer detailed description. Here we only give the core idea of the algorithm. Let us assume without loss of generality that we want to know, given a separating set of clusters, whether a simple network solution exists with reticulation number *exactly* $k$, for some constant $k$.

[[<span style="font-variant:small-caps;">Cass</span>]{}]{} tries to answer this by searching through the space of all maximal ST-set tree sequences of length at most $k$, attempting to build a network with reticulation number $k$ from each one. It looks first at shorter maximal ST-set tree sequences, padding those of length less than $k$ with empty ST-sets to attain a sequence of length exactly $k$. (As in the proof of Theorem \[thm:allbinary\], this models the situation when removing a single SBR causes the reticulation number to drop by more than 1). If there are no maximal ST-set tree sequences of length at most $k$ then [[<span style="font-variant:small-caps;">Cass</span>]{}]{} will correctly report that no solutions with reticulation number $k$ or lower exist. Hence [[<span style="font-variant:small-caps;">Cass</span>]{}]{} implicitly computes and incorporates the MST lower bound.

Assuming maximal ST-set tree sequences of length at most $k$ *do* exist, [[<span style="font-variant:small-caps;">Cass</span>]{}]{} examines each one to determine whether it can be constructively turned into a real solution. Let ${{\mathcal S}}= (S_1, \ldots, S_k)$ be a (possibly padded) maximal ST-set tree sequence of length-$k$ for ${{\mathcal C}}$. As in earlier sections we define ${{\mathcal C}}_{i}$, $1 \leq i \leq k$, as ${{\mathcal C}}\setminus S_1 \setminus \ldots \setminus 
S_{i}$, and we let ${{\mathcal C}}_{0} = {{\mathcal C}}$. [[<span style="font-variant:small-caps;">Cass</span>]{}]{} does not however work with the set ${{\mathcal C}}_{i}$. Instead it works with ${{\mathcal C}}'_{i}$ which is obtained from each ${{\mathcal C}}_{i}$ by “collapsing” *every* maximal ST-set $S$ with respect to ${{\mathcal C}}_{i}$ into a single new “meta-taxon”. This is an *extremely* greedy step, and is in some sense an attempt to generalize Corollary \[cor:maxundercut\]. The informal motivation is this: we know from Corollary \[cor:maxundercut\] that there exists some network $N$ with a minimum number of reticulations such that all maximal ST-sets are under cut-edges. Suppose we guess an SBR $T$ on ${{\mathcal X}}' \subset {{\mathcal X}}$ (where ${{\mathcal X}}'$ is a maximal ST-set) of $N$; we only have to make polynomially-many guesses because there are only polynomially-many maximal ST-sets. This gives a new network $N'$ on ${{\mathcal X}}\setminus {{\mathcal X}}'$ where perhaps not all maximal ST-sets (with respect to ${{\mathcal C}}\setminus {{\mathcal X}}'$) are under cut-edges. In particular, some SBRs of $N'$ might correspond to non-maximal ST-sets, of which there are potentially exponentially many, so how do we efficiently guess an SBR of $N'$? Fortunately, we can transform $N'$ (in the sense of Corollary \[cor:maxundercut\]) to obtain a new network $N''$ such that $r(N'') \leq r(N')$ and where all maximal ST-sets (with respect to ${{\mathcal C}}\setminus {{\mathcal X}}'$) *are* under cut-edges of $N''$. Hence we know that we again only have to make polynomially-many guesses to locate an SBR of $N''$. Furthermore, <span style="font-variant:small-caps;">Cass</span> assumes that these maximal ST-sets will always remain below cut-edges, so it collapses them into the aforementioned meta-taxa. We iterate this entire process $k$ times, concluding the “inward” phase of <span style="font-variant:small-caps;">Cass</span>. This assumption is important because it affects the “outward” phase of [[<span style="font-variant:small-caps;">Cass</span>]{}]{}, which begins immediately after completion of the inward phase. As in for example Theorem \[thm:allbinary\] the general idea is to start with a tree that represents ${{\mathcal C}}_{k}$ and then to work backwards, first trying all pairs of edges from which to “hang back” a SBR corresponding to $S_k$, then all pairs of edges (of the resulting network) from which to hang back an SBR corresponding to $S_{k-1}$, and so on, down to $S_1$. However, before hanging back each $S_i$ it first *decollapses* the maximal ST-sets that were collapsed into meta-taxa during the corresponding iteration of the inward phase.

In Section \[app:proofCassBreaks\] of the appendix we will explicitly and exhaustively walk through a specific execution of the <span style="font-variant:small-caps;">Cass</span> algorithm and this is helpful for clarifying exactly how the algorithm works.

The [[<span style="font-variant:small-caps;">Cass</span>]{}]{} algorithm is not always optimal {#subsec:cassbad}
----------------------------------------------------------------------------------------------

In this section we present a counter-example proving that the [[<span style="font-variant:small-caps;">Cass</span>]{}]{} algorithm does not always minimize level.

![Let ${{\mathcal T}}$ be the set of four trees shown here. The [[<span style="font-variant:small-caps;">Cass</span>]{}]{} algorithm returns a network $N$ that represents $Cl({{\mathcal T}})$ where $r(N)=\ell(N)=4$. However, Figure \[fig:4tL3L4\] shows that the true value of $r(Cl({{\mathcal T}})) = \ell(Cl({{\mathcal T}}))$ is at most 3.[]{data-label="fig:4t"}](./Figures/4trees.pdf)

[c]{}

  ------------------------------------ -----------------------------------------
   ![image](./Figures/4treesLev3.pdf)   ![image](./Figures/4treeCassBreaks.pdf)
                  (a)                                     (b)
  ------------------------------------ -----------------------------------------

Consider the set ${{\mathcal T}}_{4}$ of four binary trees shown in Figure \[fig:4t\]. It is easy to verify that the set ${{\mathcal C}}= 
Cl({{\mathcal T}})$ is separating and every network that represents ${{\mathcal C}}$ is thus simple or can easily be made simple. It is also easy to verify that the simple level-3 network in Figure \[fig:4tL3L4\](a) represents ${{\mathcal C}}$; in the appendix we prove that this is optimal by showing that any network that represents ${{\mathcal C}}$ must have reticulation number 3 or higher.

However, [<span style="font-variant:small-caps;">Cass</span>]{} cannot find a level-3 network. To formally prove this we show in Section \[app:proofCassBreaks\] of the appendix an exhaustive list of all possible executions of the algorithm with $k=3$. <span style="font-variant:small-caps;">Cass</span> returns the simple level-4 network shown in Figure \[fig:4tL3L4\](b). To summarize, the problem with [[<span style="font-variant:small-caps;">Cass</span>]{}]{} seems to be that while the step of always collapsing at *every* iteration *all* maximal ST-sets and treating them as meta-taxa (in the sense of Corollary \[cor:maxundercut\]) is a locally optimal move, it can force us to use too many reticulation edges when hanging (trees corresponding to) maximal ST-sets back in the outward phase.

Note that this counter-example fits in a tradition of highly specific and complex counter-examples in the phylogenetic network literature. In particular we note the very similar counter examples given initially in [@gusfielddecomp2007], and (based on this) in [@husonetalgalled2009], which showed that one cannot minimize reticulation number by optimizing independently over the connected components of the incompatibility graph $IG({{\mathcal C}})$. The relationship between these counter-examples - all of which are linked in some way or other to simple level-3 networks - seems to be that networks with minimum reticulation number have a very subtle internal structure that seems impervious to locally optimal and greedy strategies, but that these properties only start emerging for level-3 and higher.

It is important to emphasize, however, that since we could not find *any* non-synthetic dataset for which [[<span style="font-variant:small-caps;">Cass</span>]{}]{} does not find an optimal solution, we still have the feeling that [[<span style="font-variant:small-caps;">Cass</span>]{}]{} works quite well for real data.

[[<span style="font-variant:small-caps;">Cass</span>]{}]{} is optimal for sets of clusters obtained from two trees
------------------------------------------------------------------------------------------------------------------

Here we show that, despite the negative news in the previous section, [[<span style="font-variant:small-caps;">Cass</span>]{}]{} (and more generally [[<span style="font-variant:small-caps;">Cass$^{\textsc{DC}}$</span>]{}]{}) correctly minimizes level in the case of clusters obtained from two not necessarily binary trees. Furthermore the algorithms also provably minimize reticulation number.

Note that the following theorem does not contradict the NP-hardness mentioned in Corollary \[cor:boundishard\] because [[<span style="font-variant:small-caps;">Cass</span>]{}]{} only runs in polynomial time when it bounds its search to simple level-$\leq k$ networks, for a *constant* $k$.

\[thm:casscorrect\] Let ${{\mathcal C}}= Cl({{\mathcal T}})$ be a separating set of clusters where ${{\mathcal T}}$ is a set of two not necessarily binary trees on ${{\mathcal X}}$. Then [[<span style="font-variant:small-caps;">Cass</span>]{}]{} constructs a simple network $N$ that represents ${{\mathcal C}}$ such that $\ell(N) = r(N) = \ell({{\mathcal C}})= r({{\mathcal C}})$.

Let the MST lower bound for ${{\mathcal C}}$ be $p$. Recall that, by Corollary \[cor:tightbound\], in this case $p=r(N)$. We know that there is a maximal ST-set tree sequence $ (S_1, \ldots, S_p)$. As explained in Section \[subsec:casshigh\] [[<span style="font-variant:small-caps;">Cass</span>]{}]{} will eventually find this maximal ST-set tree sequence. Now, Theorem \[thm:tightbound\] essentially works by invoking Lemma \[lem:hangback\] $p$ times, and in the statement of Lemma \[lem:hangback\] there are absolutely no assumptions made about the structure of “$N$”, other than that it represents a certain set of clusters. Hence “$N$” can just as well be one of the intermediate networks constructed by <span style="font-variant:small-caps;">Cass</span>. It remains only to show that [[<span style="font-variant:small-caps;">Cass</span>]{}]{} can simulate the hanging-back construction described in the proof of Lemma \[lem:hangback\]. This is definitely so, because the proof of Lemma \[lem:hangback\] requires the edges entering two witnesses (or the edge entering one witness and, to simulate the attachment of a root edge, the edge connecting a dummy root to the real root) to be subdivided. [[<span style="font-variant:small-caps;">Cass</span>]{}]{} tries subdividing all pairs of edges, including the edge between the dummy root and the real root, and hence will eventually subdivide the correct two edges.

The proof of Theorem \[thm:casscorrect\] not only shows that [[<span style="font-variant:small-caps;">Cass</span>]{}]{} is optimal for sets of clusters obtained from two not necessarily binary trees, but also that in this very special case the “hanging back” (i.e. outward) phase of [[<span style="font-variant:small-caps;">Cass</span>]{}]{} is in some sense completely redundant. In particular: if we have already computed a maximal ST-set tree sequence, then we can easily compute a witness set for each of the maximal ST-sets in the sequence, and these witness sets directly specify a sufficient set of edges to subdivide when hanging back the maximal ST-sets. So in the case of clusters coming from two trees [[<span style="font-variant:small-caps;">Cass</span>]{}]{} wastes rather a lot of time trying to hang back maximal ST-sets from all possible pairs of edges, when in fact the information is already available to make this blind search unnecessary.\
\
Theorem \[thm:casscorrect\] can actually be re-formulated and extended to general (i.e. not necessarily separating) sets of clusters ${{\mathcal C}}$ obtained from two not necessarily binary trees. Indeed, in Theorem \[th:cassworksnonbinary\], we will prove that, for such cluster sets, [<span style="font-variant:small-caps;">Cass$^{\textsc{DC}}$</span>]{}reconstructs a network $N$ such that $r(N) = r({{\mathcal C}})$ and $\ell(N) = \ell({{\mathcal C}})$. However, we first need to prove Theorem \[thm:clusdecom\] below, which is interesting in its own right, and several auxiliary results.

\[th:cassworksnonbinary\] Let ${{\mathcal T}}=\{T_1,T_2\}$ be two not necessarily binary trees on ${{\mathcal X}}$, and let ${{\mathcal C}}= Cl({{\mathcal T}})$. When given ${{\mathcal C}}$ as input, [[<span style="font-variant:small-caps;">Cass$^{\textsc{DC}}$</span>]{}]{} computes a level-$\ell({{\mathcal C}})$ network $N$ with reticulation number $r({{\mathcal C}})$ that represents ${{\mathcal C}}$.

Observation \[obs:ccunsep\] and Theorem \[thm:clusdecom\] ensure that we can analyze each connected component of the incompatibility graph $IG({{\mathcal C}})$ separately, which (as mentioned) is exactly what [[<span style="font-variant:small-caps;">Cass$^{\textsc{DC}}$</span>]{}]{} does. (To see this it is helpful to note that any subset of ${{\mathcal C}}$ can also, with the possible exception of some superfluous singleton clusters, be expressed as the set of clusters in two trees).

Let $K$ be a connected component and denote by ${{\mathcal C}}_K$ the set of clusters in $K$. Let ${{\mathcal X}}_K$ be the set of taxa equal to the union of all clusters in ${{\mathcal C}}_K$. Note that ${{\mathcal C}}_K$ is not necessarily a tangled set. Indeed, while $IG({{\mathcal C}}_K)$ is connected, the second property of a tangled set (every pair of taxa $x$ and $y$ in ${{\mathcal X}}_K$ is separated by ${{\mathcal C}}_K$, Section \[sec:prelim\]) does not always hold. To ensure that the latter condition holds [<span style="font-variant:small-caps;">Cass$^{\textsc{DC}}$</span>]{} simply computes all the maximal ST-sets $\{S_1, ..., S_k\}$ for ${{\mathcal C}}_K$ and for each of them replaces all elements of $S_i$ with a single new taxon $s_i$ in ${{\mathcal C}}_K$, to obtain a new cluster set ${{\mathcal C}}'_K$ that is tangled.

To see that the constructed network has minimum level, observe that (by Theorem \[thm:casscorrect\]) [[<span style="font-variant:small-caps;">Cass</span>]{}]{} correctly computes minimum level solutions for the ${{\mathcal C}}'_{K}$ cluster sets mentioned above. In [@cass] it is proven that combining minimum-level solutions for the various ${{\mathcal C}}'_{K}$ yields a minimum-level solution for ${{\mathcal C}}$.

We now need to prove that the constructed network has reticulation number $r({{\mathcal C}})$. Since maximal ST-sets are unseparated and all mutually disjoint (see Corollary \[cor:mostn\]), it follows from Theorem \[thm:clusdecom\] that:\
$$r({{\mathcal C}}_K) = \displaystyle\sum_{
\begin{subarray}{c}
 \mbox{S is a maximal} \\[1mm]
 \mbox{ST-set of ${{\mathcal C}}_K$}  
\end{subarray}
}
r({{\mathcal C}}_K|S) + 
r({{\mathcal C}}'_K) .$$ Since $r({{\mathcal C}}_K|S)$ always equals zero when $S$ is an ST-set, $r({{\mathcal C}}_K) = r({{\mathcal C}}'_K)$. Moreover, since the sets ${{\mathcal X}}_K$ are also unseparated (from Observation \[obs:ccunsep\]) and all mutually disjoint, then from Theorem \[thm:clusdecom\] we have that:\
$$r({{\mathcal C}}) = \displaystyle\sum_{
\begin{subarray}{c}
 \mbox{K is a connected} \\[1mm]
 \mbox{component of $IG({{\mathcal C}})$}  
\end{subarray}
}
r({{\mathcal C}}|{{\mathcal X}}_K) + 
r({{\mathcal C}}') ,$$ where ${{\mathcal C}}'$ is obtained from ${{\mathcal C}}$ by replacing all elements of ${{\mathcal X}}_K$ with a single new taxon $x_K$. Obviously, $r({{\mathcal C}}')=0$. Since $r({{\mathcal C}}|{{\mathcal X}}_K)=r({{\mathcal C}}_K) = r({{\mathcal C}}'_K)$, and $r({{\mathcal C}}'_K)= \ell({{\mathcal C}}'_K)$ because ${{\mathcal C}}'_K$ is separating, this concludes the proof that the constructed network has reticulation number $r({{\mathcal C}})$.

[[<span style="font-variant:small-caps;">Cass</span>]{}]{} can be used to compute the hybridization number of two not necessarily binary trees\[sec:cassHybrid\]
----------------------------------------------------------------------------------------------------------------------------------------------------------------

It is important to understand the relationship between the results presented in the previous section and the extensive literature on computing the hybridization distance of two *trees* [@bordewich; @bordewich2; @sempbordfpt2007; @quantifyingreticulation; @linzsemple2009] i.e. the problem of displaying the trees themselves, and not just their clusters.

For two binary trees ${{\mathcal T}}= \{T_1, T_2\}$ on ${{\mathcal X}}$ the hybridization distance $h({{\mathcal T}})$ is defined as the minimum reticulation number $r_t({{\mathcal T}})$ of any network that displays both the trees in ${{\mathcal T}}$. In [@twotrees] we showed that $r_t({{\mathcal T}}) = r(Cl({{\mathcal T}}) )$. As discussed in [@twotrees] that means that both positive and negative results for the computation of $r_t({{\mathcal T}})$ transfer automatically to computation of $r(Cl({{\mathcal T}}))$ (for two binary trees). Negative results are NP-hardness and APX-hardness; positive results include fixed parameter tractability and running time improvements based on an increasingly deep understanding of maximum acyclic agreement forests. Before proceeding there are some technical issues regarding the definition of hybridization number of a set ${{\mathcal T}}$ of two *not necessarily binary* trees on ${{\mathcal X}}$. This can be attributed to the fact that several different definitions have appeared in the literature:

1.  $h^{+}({{\mathcal T}})$ : the minimum reticulation number of $N$ ranging over all networks $N$ that display in a strict topological sense all the trees in ${{\mathcal T}}$. This is exactly the definition of *display* given in Section \[sec:prelim\]. In Figure 8 of [@twotrees] this strict definition was used.

2.  $h^{0}({{\mathcal T}})$: the minimum reticulation number of $N$ ranging over all networks $N$ that display some not necessarily binary refinement of each tree in ${{\mathcal T}}$. Recall that a (binary) *refinement* of a tree $T$ on ${{\mathcal X}}$ is any (binary) tree $T'$ on ${{\mathcal X}}$ such that $Cl(T) \subseteq Cl(T')$. (Note that a tree is generically considered to be a refinement of itself).

3.  $h^{-}({{\mathcal T}})$: the minimum reticulation number of $N$ ranging over all networks $N$ that display a binary refinement of each tree in ${{\mathcal T}}$. This was the definition used in [@linzsemple2009].

Two of the definitions, $h^{0}$ and $h^{-}$, turn out to be equivalent. We clarify this, extend an equivalence result from [@twotrees] and thus show that [[<span style="font-variant:small-caps;">Cass$^{\textsc{DC}}$</span>]{}]{} correctly computes the hybridization number of two not necessarily binary trees in the sense of $h^{0}$, equivalently $h^{-}$. In Figure 8 of [@twotrees] a set ${{\mathcal T}}$ of two trees is given, one of which is non-binary, such that $r(Cl({{\mathcal T}})) < h^{+}({{\mathcal T}})$. A result showing that [[<span style="font-variant:small-caps;">Cass</span>]{}]{} computes $h^{+}$ was thus already excluded.

\[obs:treedefequiv\] $h^{0}({{\mathcal T}}) = h^{-}({{\mathcal T}})$ for all sets ${{\mathcal T}}$ of not necessarily binary trees on the same taxa set ${{\mathcal X}}$.

The fact that $h^{0}({{\mathcal T}}) \leq h^{-}({{\mathcal T}})$ follows immediately from the definitions. Suppose by way of contradiction that there exists a set of not necessarily binary trees ${{\mathcal T}}$ such that $h^{-}({{\mathcal T}}) > h^{0}({{\mathcal T}})$. Let $N$ be any network with reticulation number $h^{0}({{\mathcal T}})$ that displays some refinement of each tree in ${{\mathcal T}}$. Now, it is not too difficult to see (using for example the transformation described in Lemma 2 of [@twotrees]) that we can create a binary network $N'$ such that $r(N') = r(N)$ and such that $N'$ displays a binary refinement of each of the trees in ${{\mathcal T}}$, yielding a contradiction.

Given a set of trees ${{\mathcal T}}$, recall that we define $r_{tr}({{\mathcal T}})$ to be the minimum reticulation number of any network that displays $Tr({{\mathcal T}})$ (i.e. all the rooted triplets in the input trees). We have the following result:

\[theo:twotrees-1extended\] Let ${{\mathcal T}}= \{T_1,T_2\}$ be two not necessarily binary trees on ${{\mathcal X}}$. Then $h^{0}({{\mathcal T}}) = r_{tr}({{\mathcal T}})$.

Obviously, for any set ${{\mathcal T}}$ of not necessarily binary trees on ${{\mathcal X}}$, $r_{tr}({{\mathcal T}}) \leq h^{0}({{\mathcal T}})$. It remains to show that this inequality is always tight. Suppose that it is not always tight. Let then ${{\mathcal T}}= \{T_1, T_2\}$ be two smallest (in terms of the size of $|{{\mathcal X}}|=n$) trees such that $h^{0}({{\mathcal T}}) > r_{tr}({{\mathcal T}})$. Clearly $n>2$. Now, let $N_{tr}$ be any network that is consistent with $Tr({{\mathcal T}}) = R$ such that $r(N_{tr}) = r_{tr}(R)$. If $r_{tr}(R) = 0$ we have a contradiction because this only occurs if $T_1$ and $T_2$ have a common refinement, in which case $h^{0}({{\mathcal T}}) = 
0$. Hence $r_{tr}(R)>0$. This means that $N_{tr}$ has at least one SBR with taxa set $S$. Now, we claim that, for each $i \in \{1,2\}$, $S$ is the set of taxa reachable from an edge $e_i$ (in $T_i$) or as the set of taxa reachable from some subset of the children of some node $u_i$ (in $T_i$). If this is not so then there exists some triplet $xy|z$ in $R$ such that $x \not \in S$ and $y,z \in S$. However, $N_{tr}$ cannot be consistent with $xy|z$ since $S$ is the taxa set of a SBR, which by definition sits below a cut-edge, yielding a contradiction. (If $e_i$ exists assume without loss of generality that $u_i$ is its head). Let $Q' = \{v_1, \ldots, v_k\}$ be the set of children of $u_i$ such that for each $v \in Q'$, ${{\mathcal X}}(T_{v})$ contains at least one element of $S$. Now let $T'_i$ be the tree $T_i \setminus {T_{v_1}} \ldots \setminus{T_{v_k}}$ and let ${{\mathcal T}}'=\{T'_1, T'_2\}$. It is clear that $r_{tr}({{\mathcal T}}') \leq r_{tr}(R)-1$. By the assumption of minimality on $|{{\mathcal X}}|$ we have that $h^{0}({{\mathcal T}}') = 
r_{tr}({{\mathcal T}}')$. Now, let $N^{*}$ be a network with a minimum reticulation number that displays some refinement of each tree in ${{\mathcal T}}'$. Observe that there exists a binary tree $T_{S}$ on taxa set $S$ such that $T_{S}$ is a binary refinement of both $T_1|S$ and $T_2|S$, otherwise $R|S$ would not be an SBR (i.e. it would contain at least one reticulation).

But we can obtain a network with $r(N^{*})+1$ reticulations that displays some refinement of $T_1$ and $T_2$ by hanging $T_{S}$ back below a single new reticulation in $N^{*}$ such that the tails of the two reticulation edges extend the embeddings of the refinements of $T'_1$ and $T'_2$ in $N^{*}$. Hence $h^{0}({{\mathcal T}}) \leq r_{t}({{\mathcal T}}') +1 \leq r_{t}({{\mathcal T}}) < h^{0}({{\mathcal T}})$, contradiction.

The following lemma extends a result from [@twotrees]:

\[lemma:twotrees-cor2extended\] If ${{\mathcal T}}$ consists of two not necessarily binary phylogenetic trees on the same set of taxa, $r_{tr}({{\mathcal T}}) = h^{0}({{\mathcal T}})=r(Cl({{\mathcal T}}))$ .

In [@twotrees] it is proven that for a not necessarily binary set of trees ${{\mathcal T}}$ on the same set of taxa, $r_{tr}({{\mathcal T}}) \leq r(Cl({{\mathcal T}}))$. Now, if a network displays some refinement of a not necessarily binary tree $T$, then it represents all the clusters in $Cl(T)$ (and possibly more). Hence we also have that $r(Cl({{\mathcal T}})) \leq h^{0}({{\mathcal T}})$. Combining this with Theorem \[theo:twotrees-1extended\] gives the result.

Combining all these results we finally obtain the following theorem.

\[theo:casshybridnumer\] Let ${{\mathcal T}}=\{T_1,T_2\}$ be two not necessarily binary trees on ${{\mathcal X}}$, and let ${{\mathcal C}}= Cl({{\mathcal T}})$. When given ${{\mathcal C}}$ as input, [[<span style="font-variant:small-caps;">Cass$^{\textsc{DC}}$</span>]{}]{} computes a network $N$ such that $r(N)=h^{0}({{\mathcal T}})=h^{-}({{\mathcal T}})$.

Conclusion and open problems
============================

The largest open problem emerging from this article is whether there exists a “reasonable” polynomial-time algorithm for constructing phylogenetic networks of bounded reticulation number (or level) that represent a given set of clusters. The result in Section \[sec:theory\], which shows a theoretical polynomial-time algorithm for constructing networks of bounded level, does not lend itself to a real-world implementation. On the other hand we have seen that for clusters obtained from *binary* trees a relatively simple and efficient algorithm can be used. At the moment however there is no reasonable polynomial-time algorithm for general cluster sets i.e. those obtained from sets of potentially non-binary trees. We have shown that [[<span style="font-variant:small-caps;">Cass</span>]{}]{}, which has a reasonable running time, is in general not optimal (although we had to explicitly engineer a highly synthetic counter-example to determine this). [[<span style="font-variant:small-caps;">Cass</span>]{}]{} is, however, an *extremely* greedy algorithm, in the sense that at every iteration it assumes that *all* maximal ST-sets are below cut-edges. Can we relax this assumption in some way to yield a slightly less greedy version of [[<span style="font-variant:small-caps;">Cass</span>]{}]{} that is optimal? A less urgent problem, but nevertheless very interesting, is the question whether [[<span style="font-variant:small-caps;">Cass</span>]{}]{} is optimal for clusters obtained from exactly three binary trees on ${{\mathcal X}}$.

[^1]: Steven Kelk was partly funded by a Computational Life Sciences grant of The Netherlands Organisation for Scientic Research (NWO)

[^2]: Leo van Iersel was funded by the Allan Wilson Centre for Molecular Ecology and Evolution.

[^3]: Note that to determine the reticulation number of a biconnected component, the indegree of each node is computed using only edges belonging to this biconnected component.

[^4]: The presence or absence of the singleton clusters in the input does not change the complexity of the problems we study because it is trivial to modify a network without raising its reticulation number or level such that it also represents all the singleton clusters.
