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 