# Sharp upper and lower bounds on a restricted class of convex characters

Steven Kelk  and  Ruben Meuwese  Department of Data Science and Knowledge
Engineering (DKE), Maastricht University, P.O. Box 616, 6200 MD Maastricht,
The Netherlands<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Let ${\mathcal{T}}$ be an unrooted binary tree with $n$ distinctly labelled
leaves. Deriving its name from the field of phylogenetics, a _convex
character_ on ${\mathcal{T}}$ is simply a partition of the leaves such that
the minimal spanning subtrees induced by the blocks of the partition are
mutually disjoint. In earlier work Kelk and Stamoulis (_Advances in Applied
Mathematics_ 84 (2017), pp. 34–46) defined $g_{k}({\mathcal{T}})$ as the
number of convex characters where each block has at least $k$ leaves. Exact
expressions were given for $g_{1}$ and $g_{2}$, where the topology of
${\mathcal{T}}$ turns out to be irrelevant, and it was noted that for $k\geq
3$ topological neutrality no longer holds. In this article, for every $k\geq
3$ we describe tree topologies achieving the maximum and minimum values of
$g_{k}$ and determine corresponding expressions and exponential bounds for
$g_{k}$. Finally, we reflect briefly on possible algorithmic applications of
these results.

##  1\. Introduction

Consider an unrooted, undirected binary tree ${\mathcal{T}}$ where the $n$
leaves are bijectively labelled by a set $X$ of labels. In this article we are
interested in partitions of $X$ whereby the minimal spanning trees induced by
the blocks, are disjoint in ${\mathcal{T}}$. In the field of mathematical
phylogenetics, where ${\mathcal{T}}$ represents a hypothesis about the
evolutionary history of a set of contemporary species $X$ and interior nodes
represent hypothetical ancestors, such partitions are called _convex
characters_ [14]. Convex characters are of interest because they represent a
‘most parsimonious’ evolutionary scenario. Specifically, a block of the
partition can be viewed as a subset of $X$ that shares a certain trait e.g.
has a backbone. The fact that the induced spanning trees do not overlap,
models the situation whereby these traits can be extended to ancestors in
${\mathcal{T}}$, such that all contemporary and ancestral species that share
the trait form a connected component. In other words: the trait emerges once
in history; it does not vanish and re-emerge multiple times. Convex
characters, which are sometimes called _homoplasy-free_ characters due to the
absence of recurrent mutation, play a central role in the well-studied
_perfect phylogeny_ problem [11] and a number of other combinatorial and
algorithmic problems inspired by phylogenetics (e.g. [13, 6, 1]). We refer to
standard texts such as [15, 5] for more background on (mathematical)
phylogenetics.

In [12] the question was posed: how many convex characters are there on
${\mathcal{T}}$ where each block has at least $k$ leaves, denoted
$g_{k}({\mathcal{T}})$? The authors proved that for $k\in\\{1,2\\}$ the answer
is a Fibonacci number, and independent of the topology of ${\mathcal{T}}$, but
that for $k=3$ the topology of the tree does matter. This raised the question
of establishing lower and upper bounds on $g_{k}$, for $k\geq 3$.

In this article we give, for every $k\geq 3$, sharp upper and lower bounds. We
do this by identifying tree topologies that provably obtain the maximum and
minimum and determining $g_{k}$ on these trees. The maximum is attained by
caterpillar trees, and the minimum by trees we call _fully $k$-loaded trees_.
Informally, fully $k$-loaded trees are trees in which as often as possible the
leaves are organized in size $k-1$ clusters at the periphery of the tree. For
the lower bound, an exact expression is given: it grows at
$\Theta(\phi^{\frac{n}{k-1}})$ where $\phi\approx 1.618$ is the golden ratio.
For the upper bound, an exact expression and an exponential rate of growth can
be obtained by determining the real positive root of a characteristic
polynomial induced by a homogeneous linear recurrence, and then solving for
initial conditions.

In Section 2 we establish preliminaries. In Section 3 we prove the upper
bound. In Section 4 we prove the lower bound and pause briefly to study the
behaviour of $g_{3}$ between its upper and lower bounds. In Section 5 we
reflect on potential algorithmic applications of these results, noting that
algorithms listing all $g_{k}$ characters speed up considerably as $k$
increases. Finally, in Section 6 we list a number of open problems.

##  2\. Preliminaries

We note that the results in the article are not specific to phylogenetics:
they apply to undirected binary trees with distinctly labelled leaves.
However, to ensure consistency with the phylogenetics literature that inspired
the research we adopt standard phylogenetic notation.

An unrooted binary phylogenetic $X$-tree is an undirected, unrooted tree
${\mathcal{T}}=(V({\mathcal{T}}),E({\mathcal{T}}))$ where every internal
vertex has degree 3 and whose leaves are bijectively labelled by a set $X$,
where $X$ is often called the set of _taxa_ (representing the contemporary
species). All the trees in this articles are unrooted binary phylogenetic
trees, so we simply write _tree_ for brevity. We let $n=|X|$. For
$X^{\prime}\subseteq X$ we write ${\mathcal{T}}[X^{\prime}]$ to denote the
unique minimal subtree of ${\mathcal{T}}$ that spans $X^{\prime}$, and
${\mathcal{T}}|X^{\prime}$ to denote the phylogenetic tree obtained from
${\mathcal{T}}[X^{\prime}]$ by repeatedly suppressing nodes of degree 2. For
$X^{\prime}\subset X$ we define ${\mathcal{T}}\setminus X^{\prime}$ to be
${\mathcal{T}}|(X\setminus X^{\prime})$.

A _character_ $f$ on $X$ is simply a partition of $X$ into blocks (i.e. _non-
empty_ subsets) $X_{1},X_{2},...,X_{m}$. Following the phylogenetics
literature we will often refer to the blocks of the partition as _states_. We
write $X_{1}|X_{2}|...|X_{m}$ to denote that the subsets
$X_{1},X_{2},...,X_{m}$ form a partition/character of $X$. A character
$X_{1}|X_{2}|...|X_{m}$ is said to be _convex_ on ${\mathcal{T}}$ if, for each
$i\neq j$, $T[X_{i}]$ is disjoint from $T[X_{j}]$. The convexity of a
character on a tree ${\mathcal{T}}$ can be tested in polynomial [7, 9] (in
fact, linear [3]) time. For the tree ${\mathcal{T}}$ shown in Figure 1,
$abde|c|fg$ is an example of a convex character.

Figure 1. For the given tree ${\mathcal{T}}$ (on 7 taxa) there are 233 convex
characters in total, but only 8 in which each state (i.e. block of the
partition) contains at least 2 taxa, and these are shown above. Taxa connected
by grey edges are in the same state of the character. The 3 $g_{3}$ characters
are $abcdefg$, $abc|defg$ and $abcd|efg$, and the single $g_{4}$ character is
$abcdefg$.

Following [12], we define $g_{k}({\mathcal{T}})$ to be the number of convex
characters on ${\mathcal{T}}$ where each state contains at least $k$ taxa. For
shorthand we refer to such characters as $g_{k}$ characters; note that $g_{1}$
characters are just convex characters without any further restrictions. See
Figure 1 for an example. In [12] it was proven that $g_{1}({\mathcal{T}})$ and
$g_{2}({\mathcal{T}})$ are equal to the $(2n-1)$th and $(n-1)$th Fibonacci
number, respectively. This yielded the following exact expressions, where
${\mathcal{T}}$ is replaced by $n$ due to the topological neutrality, and
$\phi\approx 1.618$ is the golden ratio.

$\displaystyle g_{1}(n)$
$\displaystyle=\bigg{\lfloor}\frac{\phi^{2n-1}}{\sqrt{5}}+\frac{1}{2}\bigg{\rfloor},$
$\displaystyle g_{2}(n)$
$\displaystyle=\bigg{\lfloor}\frac{\phi^{n-1}}{\sqrt{5}}+\frac{1}{2}\bigg{\rfloor}.$

We will use the following simple observation repeatedly; it shows that for
very small $n$ (relative to $k$) $g_{k}$ is independent of topology.

######  Observation 1.

Let ${\mathcal{T}}$ be a tree on $n$ taxa. If $n<k$, $g_{k}({\mathcal{T}})=0$,
and if $k\leq n<2k$, $g_{k}({\mathcal{T}})=1$.

###### Proof.

Every character contains at least one state, and each state must have at least
$k$ taxa, so for $n<k$ no $g_{k}$ characters can exist. If $k\leq n$ we have
$g_{k}({\mathcal{T}})\geq 1$ because we can always take the unique convex
character with a single size-$n$ state. If $n<2k$ then it is not possible to
have 2 or more $g_{k}$ characters, because at least one of them would need to
have 2 or more states, and each such state must contain at least $k$ taxa. ∎

Let $A|B$ be a bipartition of $X$. We say that a tree ${\mathcal{T}}$ on $X$
contains the _split_ $A|B$ if there is a single edge of ${\mathcal{T}}$ whose
deletion disconnects ${\mathcal{T}}$ into two components, where $A$ is the set
of taxa in one component and $B$ is the set of taxa in the other. The next
observation will also be used repeatedly.

######  Observation 2.

Let ${\mathcal{T}}$ be a tree on $n$ vertices and suppose ${\mathcal{T}}$
contains a split $A|B$ such that $|B|\leq k$. Then every $g_{k}$ character of
${\mathcal{T}}$ includes a state that is a superset of $B$. If $|B|<k$, then
every $g_{k}$ character of ${\mathcal{T}}$ includes a state that is a strict
superset of $B$.

###### Proof.

Firstly, recall that every taxon in $B$ has to appear in some state. Suppose
for the sake of contradiction that there is a $g_{k}$ character such that $B$
intersects with two or more states in the character. Given that $|B|\leq k$,
each of these states contains at most $k-1$ taxa from $B$ (because each of the
states must include at least one taxon from $B$, and states are disjoint).
Hence, each of these states also contains at least one taxon from $A$. But
then the subtrees induced by these two (or more) states are not disjoint; in
particular, they both use the edge corresponding to split $A|B$, contradicting
the convexity of the character. Hence, $B$ intersects with at most one state.
If $|B|=k$, then this state must necessarily include all of $B$. If $|B|<k$
then this state must also include at least one taxon from $A$, and we are
done. ∎

The next lemma establishes a useful recurrence.

######  Lemma 3.

Suppose ${\mathcal{T}}$ contains a split $A|B$ where $|A|=k$, and let $x$ be
an arbitrary element of $A$. Then
$g_{k}({\mathcal{T}})=g_{k}({\mathcal{T}}\setminus
A)+g_{k}({\mathcal{T}}\setminus\\{x\\})$.

###### Proof.

Consider an arbitrary $g_{k}$ character $f$ of ${\mathcal{T}}$. Due to
Observation 2 and the fact that $|A|=k$, there are only two cases. In the
first case, $f$ contains a state _equal_ to $A$. There are exactly
$g_{k}({\mathcal{T}}\setminus A)$ such characters.

In the second case, $f$ contains a state $X_{i}$ that is a strict superset of
$A$, and which thus also intersects with $B$; the state contains at least
$k+1$ taxa. There are $g_{k}({\mathcal{T}}\setminus\\{x\\})$ such characters.
To see this, note that removing $x$ from $X_{i}$ gives a state that still has
at least $k$ taxa, so this yields a $g_{k}$ character for
${\mathcal{T}}\setminus\\{x\\}$. In the other direction, a $g_{k}$ character
for ${\mathcal{T}}\setminus\\{x\\}$ necessarily includes a state that contains
all of $A\setminus\\{x\\}$ and at least one taxon from $B$. Adding $x$ to this
state yields a state that contains all of $A$, and at least one taxon of $B$.
∎

##  3\. Caterpillars maximize $g_{k}({\mathcal{T}})$ for every $k\geq 1$

Figure 2. A caterpillar tree on 9 taxa.

We say that two distinct taxa $x,y$ form a _cherry_ of a tree ${\mathcal{T}}$
if they have a common parent. For $n\geq 4$ a _caterpillar_ is a tree on $n$
taxa which has exactly two cherries. Equivalently, a caterpillar is a tree
where all the degree-3 nodes form a path. See Figure 2 for an example. For
convenience we also regard the unique trees on 1, 2 or 3 taxa to be
caterpillars. We write $Cat_{n}$ to denote the caterpillar on $n\geq 1$
vertices.

We start by describing a recurrence for $g_{k}(Cat_{n})$ and then prove that
this is the maximum value of $g_{k}({\mathcal{T}})$ ranging over all trees
${\mathcal{T}}$ with $n$ taxa.

Observation 1 establishes the initial values of $g_{k}(Cat_{n})$.

######  Lemma 4.

For $n>k\geq 2$, $g_{k}(Cat_{n})=g_{k}(Cat_{n-1})+g_{k}(Cat_{n-k})$. As a
consequence, $g_{k}(Cat_{n})\in\Theta(\alpha^{n})$ where $\alpha$ is the
positive real root of the polynomial $x^{k}-x^{k-1}-1$.

###### Proof.

Due to its regular topology $Cat_{n}$ definitely contains a split $A|B$ where
$|A|=k$. Observe that ${\mathcal{T}}\setminus A$ is a caterpillar, and
${\mathcal{T}}\setminus\\{x\\}$ (for any $x\in X$) is also a caterpillar. The
recurrence now follows directly from Lemma 3. This is a homogeneous linear
recurrence; it is well understood how to solve such recurrences (see standard
textbooks such as [8]). In particular, it follows that $g_{k}(Cat_{n})$ grows
at rate $\Theta(\alpha^{n})$ where $\alpha$ is the positive real root of the
characteristic polynomial $x^{k}-x^{k-1}-1$. A precise expression for
$g_{k}(Cat_{n})$ can then be derived, if desired, by taking the initial terms
of the recurrence into account. ∎

We give an explicit example for $g_{3}$. The closed expression is:

$g_{3}(Cat_{n})=\bigg{\lfloor}0.194225...\cdot
1.46557...^{n}+\frac{1}{2}\bigg{\rfloor}$

where 1.46557… is the real solution to $x^{3}-x^{2}-1=0$. The value 0.194225…
is obtained by taking the real solution of $31x^{3}-31x^{2}+9x-1=0$ and
dividing it by $(1.46557...)^{3}$ to adjust for the fact that in this
expression $n$ refers to the number of taxa. See:
http://oeis.org/A000930111This recurrence is also known as _Narayana’s cows
sequence_..

Let $A|B|C$ be a tripartition of $X$. We say that a tree ${\mathcal{T}}$
contains $A|B|C$ if there is a degree-3 node $u$ such that $A,B,C$ are the
subsets of taxa of the three subtrees incident at $u$.

Suppose ${\mathcal{T}}$ contains a tripartition $A|B|C$ where $|A|,|B|,|C|\geq
2$. If we delete the $C$ subtree and replace it with a length-$|C|$
caterpillar inserted between the $A$ and $B$ subtrees, we obtain a new tree
${\mathcal{T}}^{\prime}$ and say that this is the result of _linearizing_ the
$C$ subtree. See Figure 3 for an example.

Figure 3. An example of the linearization operation, acting on the
tripartition $A|B|C$ of ${\mathcal{T}}$ where $A=\\{a,b,c\\}$, $B=\\{d,e,f\\}$
and $C=\\{g,h,i,j\\}$, to yield ${\mathcal{T}}^{\prime}$. Linearization
replaces subtree $C$ by a caterpillar.

######  Lemma 5.

Let $k\geq 3$. Suppose ${\mathcal{T}}$ contains a tripartition $A|B|C$ where
$|A|,|B|,|C|\geq 2$ and $|C|<k$. Let ${\mathcal{T}}^{\prime}$ be the result of
linearizing the $C$ subtree. Then $g_{k}({\mathcal{T}}^{\prime})\geq
g_{k}({\mathcal{T}})$ and ${\mathcal{T}}^{\prime}$ has fewer cherries than
${\mathcal{T}}$.

###### Proof.

The crucial fact here is that $|C|<k$. Specifically, by Observation 2, a
$g_{k}$ character $f$ for ${\mathcal{T}}$ must contain a state $X_{i}$ that
includes all of $C$ and which additionally intersects with at least one of $A$
and $B$. As a result, there is no state $X_{j}\neq X_{i}$ in $f$ that
intersects both $A$ and $B$, but not $C$ \- because then
${\mathcal{T}}[X_{j}]$ and ${\mathcal{T}}[X_{i}]$ would intersect. Hence, $f$
is also a $g_{k}$ character of ${\mathcal{T}}^{\prime}$.

The $C$ subtree contained at least one cherry, because $|C|\geq 2$; these are
all destroyed by linearization. However, no new cherries are created because
$|A|,|B|\geq 2$. ∎

######  Theorem 6.

Let $k\geq 1$. $g_{k}({\mathcal{T}})\leq g_{k}(Cat_{n})$ for every tree
${\mathcal{T}}$ on $n$ taxa.

###### Proof.

For $k\in\\{1,2\\}$ the result follows automatically because $g_{1}$ and
$g_{2}$ are invariant for topology. Henceforth we assume $k\geq 3$.

We use induction on $n+t$, where $t$ is the number of cherries in
${\mathcal{T}}$. For the base case, recall from Observation 1 that for $n<k$
we have $g_{k}({\mathcal{T}})=0$, and for $k\leq n<2k$ we have
$g_{k}({\mathcal{T}})=1$, irrespective of the topology of ${\mathcal{T}}$, so
the claim holds vacuously when $n<2k$. Now, observe that if $n+t\leq 2k$ and
$n\geq 4$, then $n<2k$ (because $t\geq 2$ in any tree with at least 4 taxa) -
so, again, by topological neutrality the claim holds. For $n\leq 3$, the
definition of $t$ is somewhat ambiguous, but however one defines it we have
$t\leq 3$, so $n+t\leq 6\leq 2k$, and the claim clearly holds for such very
small trees. Summarizing, we have shown that the claim always holds for
$n+t\leq 2k$, which concludes the base case.

Next, the inductive step. Assume that the claim holds for all trees where
$n+t\leq N$ (where $N\geq 2k$). We show that the claim holds for all trees
where $n+t\leq N+1$. Consider, therefore, a tree ${\mathcal{T}}$ where $n+t$
is equal to $N+1$. (If no such tree exists, we are immediately done). If
$n<2k$, then we are immediately done by the earlier argument. So assume that
$n\geq 2k$.

Suppose ${\mathcal{T}}$ contains a tripartition $A|B|C$ tripartition where
$|A|,|B|,|C|\geq 2$ and $|C|<k$. Then by linearizing ${\mathcal{T}}$ to obtain
${\mathcal{T}}^{\prime}$, we obtain via Lemma 5 that
$g_{k}({\mathcal{T}}^{\prime})\geq g_{k}({\mathcal{T}})$ and that
${\mathcal{T}}^{\prime}$ has fewer cherries than ${\mathcal{T}}$, but the same
number of taxa, so by induction we have $g_{k}(Cat_{n})\geq
g_{k}({\mathcal{T}}^{\prime})\geq g_{k}({\mathcal{T}})$ and we are done.

Let us therefore assume that the tripartition from the previous paragraph does
not exist. Instead, consider any tripartition $A|B|C$ such that $|A|,|B|\geq
1$, $|C|\leq k$ and $|C|$ is maximized. (Such a tripartition must exist,
because ${\mathcal{T}}$ contains a cherry, so taking $|C|=2$ is always
possible in the worst case.) We claim that $|C|=k$. Suppose this was not so,
i.e. that $2\leq|C|<k$. Then exactly one of $|A|$ and $|B|$ would be equal to
1. If neither was equal to 1, we would be in the earlier linearization case,
and if they would both be equal to 1, then $n=|A|+|B|+|C|=|C|+2\leq k+1<2k$
which is not possible due to the earlier assumption that $n\geq 2k$. So assume
without loss of generality that $|B|=1$ and $|A|\geq 2$. It follows that
${\mathcal{T}}$ contains a new tripartition $A^{\prime}|B^{\prime}|C^{\prime}$
where $|C^{\prime}|=|C|+1$, $|A^{\prime}|,|B^{\prime}|\geq 1$ and
$|A^{\prime}|+|B^{\prime}|=|A|$. However, this new tripartition yields a
contradiction to the assumption that $|C|$ was maximum:
$A^{\prime}|B^{\prime}|C^{\prime}$ also satisfies the required conditions but
has $|C|^{\prime}>|C|$ (and $|C|^{\prime}\leq k$ because $|C|<k$). So, indeed,
$|C|=k$.

Now, it follows that ${\mathcal{T}}$ contains the split $C|(A\cup B)$. Hence,
Lemma 3 can be applied to ${\mathcal{T}}$. This gives:

$g_{k}({\mathcal{T}})=g_{k}({\mathcal{T}}\setminus
C)+g_{k}({\mathcal{T}}\setminus\\{x\\})$

where $x$ is an arbitrary taxon in $C$. Tree ${\mathcal{T}}\setminus C$ has
$n-k$ taxa and less than or equal to the same number of cherries as
${\mathcal{T}}$ (because at most one new cherry can be created by pruning the
$C$ subtree, but at least one is destroyed, since $|C|=k\geq 2$). Tree
${\mathcal{T}}\setminus\\{x\\}$ has $n-1$ taxa and less than or equal to the
same number of cherries as ${\mathcal{T}}$. So the inductive claim holds for
both these two trees. So $g_{k}({\mathcal{T}}\setminus C)\leq
g_{k}(Cat_{n-k})$ and $g_{k}({\mathcal{T}}\setminus\\{x\\})\leq
g_{k}(Cat_{n-1})$. Hence, by Lemma 4 we have that $g_{k}({\mathcal{T}})\leq
g_{k}(Cat_{n})$, and we are done. ∎

######  Corollary 7.

For every $n$, the maximum value of $g_{k}$ ranging over all trees on $n$ taxa
is $g_{k}(Cat_{n})$, which is $\Theta(\alpha^{n})$, where $\alpha$ is the
positive real root of the characteristic polynomial $x^{k}-x^{k-1}-1$.

##  4\. Fully $k$-loaded trees minimize $g_{k}$ for every $k$

Having established that caterpillars maximize $g_{k}$, we now turn to the
question of the minimum. We begin with a number of auxiliary lemmas and
observations.

######  Lemma 8.

Let ${\mathcal{T}}$ be a tree on $n>k$ taxa. Then ${\mathcal{T}}$ contains a
split $A|B$ such that $k\leq|B|\leq 2(k-1)$.

###### Proof.

Pick an arbitrary taxon of ${\mathcal{T}}$ and orient the edges of
${\mathcal{T}}$ away from this taxon. We label each edge with the number of
taxa reachable from the head of this edge by directed paths (i.e. the number
of taxa on the “far” side of the split induced by this edge). Starting from
the edge incident to our chosen taxon, which has label $n-1\geq k$, we walk
onto an outgoing edge if it is labelled by a number $\geq k$ (if there are two
such edges we can break ties arbitrarily) and we continue this walk until it
cannot be extended any further. Let $e$ be the edge we have reached. At this
point both outgoing arcs from $e$ are labelled by at most $k-1$; if the label
was higher we could have continued the walk. Hence, the label of $e$ is at
most $2(k-1)$. Also, the sum of the labels on these two edges is at least $k$,
because otherwise the walk would not have reached edge $e$ in the first place.
Hence, $e$ induces a split with the desired property. ∎

######  Lemma 9.

Let ${\mathcal{T}}$ be a tree on $n\geq 3k-2$ taxa. Then
$g_{k}({\mathcal{T}})\geq 2$.

###### Proof.

Let $A|B$ be the split whose existence is guaranteed by Lemma 8. Due to the
fact that $k\leq|B|\leq 2k-2$, we have that
$|A|\geq|X|-(2k-2)\geq(3k-2)-(2k-2)\geq k$. Hence, the character with two
states, $A$ and $B$, is definitely a $g_{k}$ character. Combined with the fact
that $X$ (i.e. the character with a single size-$n$ state) is vacuously also a
$g_{k}$ character, we have that $g_{k}({\mathcal{T}})\geq 2$. ∎

We say that a tree ${\mathcal{T}}$ on $n$ vertices is _fully $k$-loaded_ if it
can be created by the following process, which is schematically illustrated in
Figure 4. First, select a tree $S$ on $\lceil\frac{n}{k-1}\rceil$ taxa, we
call this the _scaffold_ tree. If $n\text{ mod }(k-1)=0$, we replace each leaf
of $S$ with a subtree on $k-1$ taxa. If $n\text{ mod }(k-1)\neq 0$, we replace
all but one of the leaves of $S$ with a subtree on $k-1$ taxa, and the
remaining leaf with a subtree on $n\text{ mod }(k-1)$ taxa. We call this
remaining subtree, if it exists, the _residue_ subtree (and the corresponding
leaf of the scaffold the _residue leaf_). We note that the subtrees used in
this process, do not have to have the same topology, and that at least one
fully $k$-loaded tree exists for every $n$. We will write _fully loaded tree_
when $k$ is implicit from the context.

Figure 4. The tree on the left is a scaffold tree with 4 vertices. If $n\text{
mod }(k-1)=0$, then each of its 4 leaves is replaced by a subtree on $k-1$
taxa, depicted as white triangles in the top tree. If $n\text{ mod }(k-1)\neq
0$, then exactly one of these subtrees is allowed to have $n\text{ mod }(k-1)$
taxa - this is the residue subtree - shown as a black triangle in the bottom
tree.

As an explicit example, consider the tree in Figure 1. This is a fully
$4$-loaded tree, because you could obtain it from the (unique) scaffold tree
on 3 leaves, by attaching subtrees with taxa $\\{a,b,c\\}$, $\\{e,f,g\\}$ and
$\\{d\\}$ to the leaves of the scaffold. In this case, $\\{d\\}$ would be the
residue subtree, because it does not contain exactly $4-1=3$ taxa. The tree is
actually also fully $5$-loaded, by taking a single edge as the scaffold, and
attaching subtrees on $\\{a,b,c,d\\}$ and $\\{e,f,g\\}$ (where here
$\\{e,f,g\\}$ is the residue). However, the tree is not a fully $3$-loaded
tree, because more than one of its taxa are not in cherries.

######  Lemma 10.

Let ${\mathcal{T}}$ be a fully $k$-loaded tree on $n$ taxa and $S$ be a
corresponding scaffold tree. Then
$g_{k}({\mathcal{T}})=g_{2}(S)=g_{2}(\lceil\frac{n}{k-1}\rceil)$. In
particular: all fully $k$-loaded trees on $n$ taxa have the same $g_{k}$
value.

###### Proof.

Recall that, in the process of constructing ${\mathcal{T}}$ from $S$, at most
one of the leaves of $S$ is replaced with a subtree with strictly fewer than
$k-1$ taxa; all other leaves are replaced by subtrees with _exactly_ $k-1$
taxa. Now, each state in a $g_{2}$ character of $S$ contains at least 2 leaves
of $S$, so at least one of these leaves corresponds to a subtree of
${\mathcal{T}}$ with exactly $k-1$ taxa (and the other leaf corresponds to a
subtree of ${\mathcal{T}}$ with at least 1 taxon). Hence, when this $g_{2}$
character is mapped to a character of ${\mathcal{T}}$ each state in the
character of ${\mathcal{T}}$ has at least $k$ taxa i.e. it is a $g_{k}$
character.

In the other direction, consider an arbitrary $g_{k}$ character of
${\mathcal{T}}$. The subtrees of ${\mathcal{T}}$ corresponding to leaves of
$S$ all have at most $k-1$ taxa, so any $g_{k}$ character of ${\mathcal{T}}$
must intersect with taxa from at least two such subtrees. When projected back
to a character $S$ in the natural fashion, this induces a character of $S$
that has at least two leaves per state.

The second inequality follows from [12], where it is established that $g_{2}$
depends only on $n$, and not the topology of the tree. ∎

A subtree of ${\mathcal{T}}$ is _pendant_ if it can be detached from
${\mathcal{T}}$ by deleting a single edge. The subtrees attached in the
construction of fully loaded trees are all pendant, for example. The following
lemma, which applies to all trees, shows that the topology of “small’ (with
respect to $k$) pendant subtrees is irrelevant for determining $g_{k}$.

######  Lemma 11.

Let ${\mathcal{T}}$ be a tree on $n>k$ taxa. Suppose ${\mathcal{T}}$ contains
a split $A|B$ where $|B|\leq k$. Let ${\mathcal{T}}^{\prime}$ be the tree
obtained by replacing the $B$ subtree with an arbitrary other subtree on the
same subset of taxa. Then
$g_{k}({\mathcal{T}})=g_{k}({\mathcal{T}}^{\prime})$.

###### Proof.

This is a direct consequence of Observation 2. ∎

Our final auxiliary lemma shows that “moderately large” pendant subtrees (with
respect to $k$) can be replaced by subtrees that, in a local sense, are fully
$k$-loaded, _without increasing $g_{k}$_.

######  Lemma 12.

Let ${\mathcal{T}}$ be a tree on $n$ taxa. Suppose ${\mathcal{T}}$ contains a
split $A|B$ such that $k\leq|B|\leq 2(k-1)$. Consider the unique fully
$k$-loaded tree $\mathcal{F}$ on $|B|$ taxa obtained from the scaffold tree
that is just a single edge $e$. Create a new tree ${\mathcal{T}}^{\prime}$ on
$n$ taxa by replacing the size-$|B|$ subtree of ${\mathcal{T}}$, with
$\mathcal{F}$, where $\mathcal{F}$ is attached by subdividing $e$. Then
$g_{k}({\mathcal{T}})\geq g_{k}({\mathcal{T}}^{\prime})$.

###### Proof.

Note that, due to our choice of where to attach $\mathcal{F}$, the subtree
$\mathcal{F}$ (when viewed as part of ${\mathcal{T}}$) consists of two
subtrees: one containing exactly $k-1$ taxa, and the other containing at most
$k-1$ taxa. Every $g_{k}$ character of ${\mathcal{T}}^{\prime}$ must have a
state that includes all the taxa from both subtrees: this is a consequence of
applying Observation 2 to both the subtrees. Any such character is also a
$g_{k}$ character for ${\mathcal{T}}$. ∎

We now move towards our main result. The following lemma establishes the base
case of the induction proof used in Theorem 14.

######  Lemma 13.

For $k\leq n\leq 4k-4$, there exists a fully $k$-loaded tree on $n$ vertices
that minimizes $g_{k}$.

###### Proof.

For $k\leq n\leq 2k-1$ this is immediate from Observation 1 and the fact that
fully $k$-loaded trees exist for every $n$. For $2k\leq n\leq 3k-3$, observe
that any fully $k$-loaded tree ${\mathcal{T}}$ obtained from the unique
scaffold tree on 3 leaves (i.e. the star tree with single degree-3 node
incident to 3 leaves), has $g_{k}({\mathcal{T}})=1$ which is minimal. For
$3k-2\leq n\leq 4k-4$, observe that a fully $k$-loaded tree ${\mathcal{T}}$
obtained from the unique scaffold tree on 4 vertices, has
$g_{k}({\mathcal{T}})=2$. This must be minimum, due to the lower bound
established by Lemma 9. ∎

######  Theorem 14.

Let $n\geq k$. Every fully $k$-loaded tree ${\mathcal{T}}$ on $n$ taxa is a
minimizer for $g_{k}$.

###### Proof.

We prove this by induction. Our inductive claim is not that _every_ fully
$k$-loaded tree on $n$ taxa is minimum, but that _at least one_ is. The
strengthening to _every_ will then follow automatically from Lemma 10. We
assume $k\geq 3$, because for $k\in\\{1,2\\}$ the result is immediate due to
topological neutrality.

For the base case we take $n\leq 4k-4$. This is proven by Lemma 13.

Now, assume that for all $n\leq N$ the claim holds, where $N\geq 4k-4$. Let
${\mathcal{T}}$ be an arbitrary tree on $n=N+1$ taxa that minimizes $g_{k}$.
From Lemma 8, there exists a split $E|F$ in ${\mathcal{T}}$ such that
$k\leq|F|\leq 2(k-1)$. By applying Lemma 12, we obtain a new tree
${\mathcal{T}}^{\prime}$ on the same number of taxa (that also contains the
split $E|F$) such that $g_{k}({\mathcal{T}})\geq
g_{k}({\mathcal{T}}^{\prime})$, so ${\mathcal{T}}^{\prime}$ is also a
minimizer – because by assumption ${\mathcal{T}}$ was a minimizer. For ease of
notation, we will take ${\mathcal{T}}={\mathcal{T}}^{\prime}$ in the rest of
the proof.

Crucially, by construction, the $F$ subtree of ${\mathcal{T}}$ now consists of
one subtree containing _exactly_ $k-1$ taxa, and one subtree containing at
least 1 and _at most_ $k-1$ taxa. Hence, ${\mathcal{T}}$ contains a
tripartition $A|B|C$ where $|B|=k-1$ and $1\leq|C|\leq k-1$ and
$|A|>2(k-1)\geq k$ (where the last inequality follows because $n>N\geq 4k-4$
and $k\geq 3$). Let $a,b,c$ be the cardinalities of $A,B,C$ respectively.

The following recurrence holds222The recurrence could actually be simplified
because $g_{k}({\mathcal{T}}|C)=0$, by virtue of the fact that $c<k$, and
$g_{k}({\mathcal{T}}|B\cup C)=1$, because $k\leq b+c<2k$. However, this
simplification is not necessary for the proof and obfuscates the origin of the
recurrence., because $b=k-1$:

(1) $\displaystyle g_{k}({\mathcal{T}})=g_{k}({\mathcal{T}}|A\cup
B)g_{k}({\mathcal{T}}|C)+g_{k}({\mathcal{T}}|A)g_{k}({\mathcal{T}}|B\cup
C)+g_{k}({\mathcal{T}}|A\cup B)g_{k}({\mathcal{T}}|B\cup C).$

The three terms of the recurrence are based on Observation 2 i.e. that every
character we wish to count has a state that is a _strict_ superset of $B$.
Such a state must also intersect with (i) $A$ (but not $C$), or (ii) $C$ (but
not $A$) or (iii) both. The third term, which models (iii), requires a little
explanation. It is correct because every such state can be decomposed into a
part that intersects both $B$ and $A$, and a part that intersects both $B$ and
$C$; both these parts have size at least $k$. In the other direction, $g_{k}$
characters for ${\mathcal{T}}|A\cup B$ (respectively, ${\mathcal{T}}|B\cup C$)
necessarily contain a state that contains all of $B$, and at least one taxon
from $A$ (respectively, $C$), so every pairing of a $g_{k}$ character from
${\mathcal{T}}|A\cup B$ with a $g_{k}$ character from ${\mathcal{T}}|B\cup C$
yields a character of type (iii).

Note that $a,b,c,a+b,b+c$ are all strictly less than $n$, so the inductive
claim holds for all trees restricted to subsets of taxa of these sizes. Let
$g_{k}^{fl}(n)$ denote the value of $g_{k}$ for a fully $k$-loaded tree on $n$
taxa; as proven earlier this is independent of topology. By induction we
therefore have,

(2) $\displaystyle g_{k}({\mathcal{T}})\geq
g_{k}^{fl}(a+b)g_{k}^{fl}(c)+g_{k}^{fl}(a)g_{k}^{fl}(b+c)+g_{k}^{fl}(a+b)g_{k}^{fl}(b+c).$

The next part of the proof has two phases of applying the inductive
hypothesis. If at least one of $a$ and $c$ is divisible by $k-1$, then only
the first phase will be necessary.

We create a new tree ${\mathcal{T}}^{\prime}$ on $n$ taxa by doing the
following. We replace the $A$ subtree with an arbitrary fully $k$-loaded tree
on $a$ taxa. The attachment point of this fully loaded tree should be a
subdivided edge of its underlying scaffold tree. (This is necessary to avoid
that we accidentally attach it “inside” one of its size-($k-1$) subtrees,
which would destroy its fully $k$-loaded structure). Note that such a scaffold
tree definitely contains at least one edge, because $a\geq k$. Moreover, if
$a$ is not divisible by $k-1$, we must use as attachment point a subdivision
of the unique edge of the underlying scaffold tree that feeds into the residue
leaf: in Figure 4 this would mean the edge feeding into the black triangle.
(The significance of this will be explained later).

We leave the $B$ and $C$ subtrees untouched. This completes the construction
of ${\mathcal{T}}^{\prime}$.

Observe that the subtrees ${\mathcal{T}}^{\prime}|A\cup B$,
${\mathcal{T}}^{\prime}|C$, ${\mathcal{T}}^{\prime}|B\cup C$,
${\mathcal{T}}^{\prime}|A$ are all fully $k$-loaded; for
${\mathcal{T}}^{\prime}|B\cup C$ and ${\mathcal{T}}^{\prime}|A\cup B$ this
follows because $b=k-1$ and (for ${\mathcal{T}}^{\prime}|A\cup B$) because of
our choice of attachment point. ${\mathcal{T}}^{\prime}|A$ is fully $k$-loaded
by construction, and ${\mathcal{T}}^{\prime}|C$ is vacuously fully $k$-loaded
because $1\leq c<k$. Hence, $g_{k}({\mathcal{T}}^{\prime})$ is identical to
the right hand side of inequality (2). Hence, $g_{k}({\mathcal{T}})\geq
g_{k}({\mathcal{T}}^{\prime})$, so due to the fact that we assumed that
${\mathcal{T}}$ was a minimizer, ${\mathcal{T}}^{\prime}$ is also a minimizer.
Now, if at least one of $a$ and $c$ is divisible by $k-1$, it follows that
${\mathcal{T}}^{\prime}$ is not only a minimizer, but also a fully $k$-loaded
tree, so the proof is complete.

If neither $a$ nor $c$ is divisible by $k-1$, then ${\mathcal{T}}^{\prime}$
will not be fully $k$-loaded. This is because the $A$ part of
${\mathcal{T}}^{\prime}$ will contain a residue subtree, and the $C$ part of
${\mathcal{T}}^{\prime}$ is (entirely) a residue subtree, yielding two residue
subtrees in total; a fully $k$-loaded tree has at most one residue subtree. In
this situation, depicted in Figure 5, a second phase of induction is necessary
to “clean up” these unwanted subtrees. Observe that $a>2k-2$, so the
underlying scaffold tree for $A$ has at least 3 leaves (because a fully
$k$-loaded tree with an underlying scaffold consisting of just 2 leaves, can
have at most $2(k-1)$ taxa). Hence, the underlying scaffold tree contains a
cherry, such that neither leaf of the cherry is a residue leaf. In more
detail: if the scaffold has 4 or more leaves, it will have at least 2
cherries, and the residue leaf can be part of at most one of them. If the
scaffold has 3 leaves, then any pairing of 2 leaves forms a cherry, so take
the 2 non-residue leaves.

Figure 5. If neither $|A|$ nor $|C|$ is divisible by $k-1$, then
${\mathcal{T}}^{\prime}$ will not yet be fully loaded, due to having _two_
residue subtrees (shown as black triangles). In this case a second application
of induction is required.

Hence, both leaves of this cherry expand to subtrees with exactly $k-1$ taxa.
By construction the attachment point explicitly avoids both these subtrees and
the two edges feeding into them; this is the significance of the earlier
careful choice of attachment location in the case that $a$ is not divisible by
$k-1$. As a result, these two subtrees with $k-1$ taxa have a common parent in
${\mathcal{T}}^{\prime}$ (this is the node $u$ in Figure 5). This means that
${\mathcal{T}}^{\prime}$ contains a tripartition
$A^{\prime}|B^{\prime}|C^{\prime}$ where $|B^{\prime}|=|C^{\prime}|=k-1$, by
taking these two size $k-1$ subtrees as $B^{\prime}$ and $C^{\prime}$. We
repeat the original induction argument with this new tripartition, yielding a
new tree ${\mathcal{T}}^{\prime\prime}$ with the property that
$g_{k}({\mathcal{T}}^{\prime})\geq g_{k}({\mathcal{T}}^{\prime\prime})$. Due
to the fact that (at least) two parts of the new tripartition are divisible by
$k-1$, ${\mathcal{T}}^{\prime\prime}$ will be fully $k$-loaded (i.e. we will
only need the first phase of the proof), and a minimizer, so the inductive
claim follows. ∎

######  Corollary 15.

For $n\geq k\geq 2$, the minimum value of $g_{k}$ ranging over all trees on
$n$ taxa is exactly

$\bigg{\lfloor}\frac{\phi^{\lceil\frac{n}{k-1}\rceil-1}}{\sqrt{5}}+\frac{1}{2}\bigg{\rfloor}.$

###### Proof.

Recall from the preliminaries that an exact expression for $g_{2}$ is

$\displaystyle g_{2}(n)$
$\displaystyle=\bigg{\lfloor}\frac{\phi^{n-1}}{\sqrt{5}}+\frac{1}{2}\bigg{\rfloor}.$

The desired new expression is obtained by substituting
$\lceil\frac{n}{k-1}\rceil$ for $n$ in the $g_{2}$ expression (see Lemma 10),
while Theorem 14 establishes that this is indeed minimum. ∎

Returning to our concrete example of $g_{3}$, this yields a minimum of
$\Theta(\phi^{n/2})$, so $\Theta(1.272^{n})$, contrasting with the
caterpillar-induced maximum of $\Theta(1.466^{n})$. Given the gap between the
maximum and minimum, it is reasonable to conjecture that $g_{3}$ drops
smoothly as the number of cherries $t$ in the tree increases (because fully
$3$-loaded trees consist primarily of cherries, with at most 1 taxon not in a
cherry). The following bound shows that this is _partially_ the case.

######  Lemma 16.

Let ${\mathcal{T}}$ be a tree on $n$ taxa with $t$ cherries. Then
$g_{3}({\mathcal{T}})$ is $O(\phi^{n-t})$.

###### Proof.

Let ${\mathcal{T}}^{\prime}$ be the fully $3$-loaded tree obtained from
${\mathcal{T}}$ by doubling the $n-2t$ taxa not in cherries.
${\mathcal{T}}^{\prime}$ has $n+(n-2)t=2n-2t$ taxa. This is even, so from
Lemma 10 we have that,

$\displaystyle g_{3}({\mathcal{T}}^{\prime})$
$\displaystyle=\bigg{\lfloor}\frac{\phi^{n-t-1}}{\sqrt{5}}+\frac{1}{2}\bigg{\rfloor}.$

Observe that every $g_{3}$ character of ${\mathcal{T}}$ naturally maps
injectively to a $g_{3}$ character of ${\mathcal{T}}^{\prime}$, by putting
each newly added taxon into the same state as its sibling. Hence
$g_{3}({\mathcal{T}})\leq g_{3}({\mathcal{T}}^{\prime})$ and the result
follows. ∎

Although the upper bound given above does converge on the true minimum
(consider $t=n/2$), it remains quite weak, in the sense that once $t$ falls
below (roughly) $n/5$, the caterpillar upper bound of $O(1.466^{n})$ is
stronger. It would be interesting to develop tighter upper bounds when $t$ is
comparatively small compared to $n$.

##  5\. Applications

We note in the table below minimum and maximum values of $g_{k}$, for the
first few values of $k$. Each entry $\alpha$ indicates that the minimum
(respectively, maximum) grows at rate $\Theta(\alpha^{n})$. For $k\geq 3$ we
have used the results in this article: fully loaded $k$-trees determine the
minimum and caterpillars determine the maximum.

| _minimum_ | _maximum_
---|---|---
$g_{1}$ | 2.618 | 2.618
$g_{2}$ | 1.618 | 1.618
$g_{3}$ | 1.272 | 1.466
$g_{4}$ | 1.174 | 1.380
$g_{5}$ | 1.128 | 1.325
$g_{6}$ | 1.101 | 1.285

The numbers in the right column, let us denote these $\alpha_{k}$, have an
algorithmic significance. Any algorithm that functions by looping through all
the $g_{k}$ characters, and performing polynomial-time computation on each
such character, will have a worst-case running time of the form
$O(\alpha_{k}^{n}\cdot\text{poly}(n))$. This is a consequence of the results
from [12], where it is shown how to compute $g_{k}$ in polynomial time, and
(relatedly) how to list all $g_{k}$ characters in time
$\Theta(g_{k}({\mathcal{T}})\cdot\text{poly}(n))$. Clearly, this worst-case
running time will decrease as $k$ increases.

This raises the question of how scalable such algorithms can be in practice.
To answer this, we took the code from [12] and for $1\leq k\leq 6$ used it to
determine the highest $n$ for which all $g_{k}$ characters could be listed
within 1, 10 or 100 seconds. We did this twice: once on caterpillar trees, and
once on randomly generated trees (which are typically far from being
caterpillars due to being fairly balanced). The random trees were generated
following the protocol described in [16]. The results are below333The
experiment was conducted within the Linux Subsystem (Ubuntu 16.04.6 LTS),
running under Windows 10, on a 64-bit HP Envy Laptop 13-ad0xx (quad-core
i7-7500 @ 2.7 GHz), with 8 Gb of memory..

| _caterpillar_ | _random trees_
---|---|---
| 1s | 10s | 100s | 1s | 10s | 100s
$g_{1}$ | 14 | 16 | 19 | 14 | 16 | 19
$g_{2}$ | 27 | 32 | 37 | 27 | 32 | 37
$g_{3}$ | 34 | 41 | 47 | 38 | 49 | 55
$g_{4}$ | 40 | 48 | 56 | 56 | 66 | 74
$g_{5}$ | 47 | 56 | 64 | 73 | 84 | 96
$g_{6}$ | 52 | 63 | 72 | 83 | 101 | 116

We see that, for $k\geq 3$, the listing algorithms scale somewhat better on
random trees than on caterpillars. Beyond extremely small $n$, real
phylogenetic trees inferred from biological data rarely reach either
topological extreme, so for such trees it is realistic to expect an
intermediate level of scalability.

Although the running times remain prohibitive for larger trees, they are still
quite encouraging by the standards of exponential-time algorithms. This was
noted in [12] where an algorithm based on listing $g_{2}$ characters was used
to design a simple but surprisingly practical algorithm for exact computation
of _maximum parsimony distance_ [6] on two phylogenetic trees. This later
became the foundation for a far more scalable sampling-based heuristic for the
same problem [16]; both the listing and sampling leverage the dynamic
programming scaffolding originally used to actually count $g_{k}$. In [12] it
was also observed that the _maximum agreement forest_ problem [2] can be
solved in time $O(2.619^{n})$ by listing $g_{1}$ characters. One can think of
an agreement forest on a set of trees as a character that is convex on all
trees and where the states induce the same topologies across all trees. There
are many convex characters that do not induce agreement forests, but -
crucially - every agreement forest _does_ induce a convex character.

Indeed, any optimization or decision problem that ‘projects down’ onto convex
characters, can potentially be tackled by such listing algorithms. The
flexibility of such an approach is that one only requires an algorithm to
check whether a convex character actually has the desired, typically stronger,
property, and thus little time needs to be spent on algorithm design or
research. The new upper bounds given in this article additionally allow us to
bound the worst-case running time of such algorithms. Some simple examples of
problems that could easily be modelled within this ‘convex character
programming’ framework are listed below. In all cases we assume the input is a
set of phylogenetic trees $\mathbb{T}$ on $X$ whereby $|\mathbb{T}|$ is
$O(\text{poly}(n))$. The notation $O^{*}(.)$ denotes that polynomial factors
are suppressed.

  * •

_Partition problems with lower bounds:_ Compute an agreement forest for
$\mathbb{T}$ with a minimum number of components, such that every component of
the forest contains at least $k$ taxa, or state that no such forest exists.
Here $g_{k}$ can be used, yielding a running time of $O^{*}(\alpha_{k}^{n})$.
Generalizes easily to the variant where disjointness is only required in one
or more of the input trees.

  * •

_Exact partition problems:_ Determine whether it is possible to perfectly
partition $X$ into size-4 blocks, such that in each tree in $\mathbb{T}$ the
induced size-4 subtrees (“quartets”) are disjoint and have the same topology.
Here $g_{4}$ can be used, yielding a running time of $O^{*}(1.38^{n})$.

  * •

_Character inference problems subject to an objective function:_ Let
${\mathcal{T}}$ be a specified tree in the input set $\mathbb{T}$. Find a
$g_{k}$ character $f$ on ${\mathcal{T}}$ that optimizes a polynomial-time
computable objective function $Z(f,\mathbb{T})$, such as sum of parsimony
scores, or sum of log likelihoods subject to a chosen statistical model of
evolution. Here $g_{k}$ can be used, yielding a running time of
$O^{*}(\alpha_{k}^{n})$. Can be generalized to the case when
${\mathcal{T}}\in\mathbb{T}$ is not given and the choice of tree from
$\mathbb{T}$ needs to be co-optimized.

##  6\. Future work

It would be particularly interesting to quantify the growth of $g_{k}$ between
the two topological extremes of fully $k$-loaded trees and caterpillars. For
$g_{3}$, for example, it is clear that the value drops towards its minimum as
the number of cherries in a tree increases, but as discussed earlier it is
only a partial explanation for the behaviour of $g_{3}$. Thus, it is necessary
to identify which topological features of trees, if any, are sufficient (and
possibly necessary) to yield a decrease in $g_{k}$. It would also be
interesting to dive deeper into a question posed in [12]: what are necessary
and sufficient conditions for two non-isomorphic trees on $n$ taxa to induce
the same vector of $g_{k}$ values? How might such a vector of $g_{k}$ values
change under the action of _tree rearrangement_ operations? These are commonly
used to heuristically navigate through the space of trees in the process of
inferring phylogenetic trees from sets of characters [10]; see [4] for similar
questions.

##  7\. Acknowledgements

Ruben Meuwese was supported by the Dutch Research Council (NWO) KLEIN 1 grant
_Deep kernelization for phylogenetic discordance_ , project number
OCENW.KLEIN.305.

## References

  * [1] N. Alexeev and M. Alekseyev.  Combinatorial scoring of phylogenetic trees and networks based on homoplasy-free characters.  Journal of Computational Biology, 25(11):1203–1219, 2018.
  * [2] B. Allen and M. Steel.  Subtree transfer operations and their induced metrics on evolutionary trees.  Annals of Combinatorics, 5:1–15, 2001.
  * [3] E. Bachoore and H. Bodlaender.  Convex recoloring of leaf-colored trees.  Utrecht University technical report, 2006.
  * [4] D. Bryant.  The splits in the neighborhood of a tree.  Annals of Combinatorics, 8(1):1–11, 2004.
  * [5] J. Felsenstein.  Inferring Phylogenies.  Sinauer Associates, Incorporated, 2004.
  * [6] M. Fischer and S. Kelk.  On the maximum parsimony distance between phylogenetic trees.  Annals of Combinatorics, 20(1):87–113, 2016.
  * [7] W. Fitch.  Toward defining the course of evolution: minimum change for a specific tree topology.  Systematic Zoology, 20(4):406–416, 1971.
  * [8] R. Graham, D. Knuth, and O. Patashnik.  Concrete Mathematics: A Foundation for Computer Science.  Addison-Wesley, 1989.
  * [9] J. Hartigan.  Minimum mutation fits to a given tree.  Biometrics, pages 53–65, 1973.
  * [10] K. St John.  The shape of phylogenetic treespace.  Systematic Biology, 66(1):e83, 2017.
  * [11] S. Kannan and T. Warnow.  A fast algorithm for the computation and enumeration of perfect phylogenies.  SIAM Journal on Computing, 26(6):1749–1763, 1997.
  * [12] S. Kelk and G. Stamoulis.  A note on convex characters, fibonacci numbers and exponential-time algorithms.  Advances in Applied Mathematics, 84:34–46, 2017.
  * [13] S. Moran and S. Snir.  Efficient approximation of convex recolorings.  Journal of Computer and System Sciences, 73(7):1078–1089, 2007\.
  * [14] C. Semple and M. Steel.  Phylogenetics. Oxford University Press, 2003.
  * [15] M. Steel.  Phylogeny: Discrete and Random Processes in Evolution.  SIAM, 2016.
  * [16] R. van Wersch, S. Kelk, S. Linz, and G. Stamoulis.  Reflections on kernelizing and computing unrooted agreement forests.  arXiv preprint arXiv:2012.07354, 2020.