# Partitioning a binary tree into vertex-disjoint subtrees

Say we have a labeled, binary unrooted tree $T$, i.e. each node has either 1 or 3 neighbors.
Denote by $L(T)$ the set of leaves (degree-one nodes) of $T$.

For some $L \subseteq L(T)$, denote by $t(L)$ the smallest subtree of $T$ containing $L$. That is, $t(L)$ is the minimal (in terms of nodes) connected induced subgraph of $T$ that contains $L$.

A $k$-partition $P = \{L_1, \ldots, L_k\}$ of $L(T)$ is called valid if for any distinct $L_i, L_j \in P$, $t(L_i)$ and $t(L_j)$ are vertex-disjoint.

The question is : how many valid $k$-partitions of $L(T)$ does $T$ have ? Denote by $p(T)$ the number of such partitions.

I'd like to know if this problem is known/has been addressed previously.

I'd be happy with lower and upper bounds on $p(T)$. I'd also like to know if the structure of $T$ is relevant, or is $p(T)$ only dependent on $|L(T)|$ ?

NOTE : this originates from this thing called the Perfect Phylogeny Problem, which has been studied for some time - but no one seems to have bothered with counting $p(T)$.

• I don't know about useful bounds, but in general $p(T)$ will not be a function of $|L(T)|$ alone. To see this, you can find two non-isomorphic trees, each with ten nodes and $|L(T)| = 6$, that have different values for $p(T)$. Jun 9 '15 at 14:05
• @WillBrian: It turns out that $p(T)$ is, in fact, a function of $|L(T)|$ as was first discovered by Steel (1992). Details are given in the new answer below. Feb 10 '16 at 2:44
• @MaxAlekseyev: I revisited my example this morning, and I think I must have simply miscounted the valid partitions for one (or both) of the trees the first time around. It seems you are certainly right -- thanks for correcting my mistake. Feb 10 '16 at 15:13

UPDATE. My original answer addressed the case when $t(L)$ is defined as the minimal binary subtree (which may be rooted, i.e. have one vertex of degree 2). This is now posed as Case 1.

Case 2 down below addresses the case when $t(L)$ is the minimal arbitrary subtree (i.e., connected acyclic graph).

Case 1. $t(L)$ is a binary subtree.

Each valid partition corresponds to a binary subtree of the given tree. Namely, let $T'$ be a binary subtree of $T$. If $T'$ consists of a single edge $t$, then this edge defines of a $2$-partition of $L(T)$ obtained by removal of $t$ from $T$, which splits $L(T)$ into two complementary subsets.

More generally, $T'$ with $k>2$ leaves defines a $k$-partition of $L(T)$ as follows. Every leaf $t$ of $T'$ corresponds to a subset of $L(T)$: removal of the leaf edge of $t$ in $T'$ from $T$ splits $T$ into two subgraphs, one of which is edge-disjoint with $T'$. The set of leaves of this subgraph defines a subset $L_t$ of $L(T)$. It is clear that $L_{t_1}$ and $L_{t_2}$ are disjoint for any distinct leaves $t_1$ and $t_2$ of $T'$. Furthermore, each leaf of $T$ belongs to $L_t$ for some leaf $t$ of $T$. That is, the sets $L_t$, where $t$ runs over the leaves of $T'$, form a valid $k$-partition of $L(T)$.

Here is a modification of the algorithm from Counting the number of subgraphs in a given labeled tree that counts the number of binary subtrees with $k$ leaves in the given binary $T$.

Let $\ell$ be a fixed leaf of $T$ and $r$ be its the only neighbor. Let $T_r$ be a rooted binary tree obtained from $T$ by removal of $\ell$, with the root at $r$. More generally, let $T_v$ denote the subtree of $T_r$, rooted at vertex $v$.

For a vertex $v$ in $T_r$, define $$A_v(z)=a_1\cdot z+a_2\cdot z^2+\dots,$$ $$B_v(z)=b_1\cdot z+b_2\cdot z^2+\dots,$$ where $a_i$ is the number of binary subtrees of $T_v$ that have $i$ leaves and include $v$; and similarly, $b_i$ is the number of binary subtrees of $T_v$ that have $i$ leaves and do not include $v$.

If $v$ is a leaf then $A_v(z)=z$ and $B_v(z)=0$.

If $u_1,u_2$ are the children of a non-leaf $v$, then $$\begin{cases} A_v(z) = z + A_{u_1}(z)\cdot A_{u_2}(z), \\ B_v(z) = A_{u_1}(z) + B_{u_1}(z) + A_{u_2}(z) + B_{u_2}(z), \end{cases}$$ and the answer is the coefficient of $z^{k-1}$ in $$A_r(z)+B_r(z).$$ Here we account for the fact that rooted binary subtrees in $T_r$ with $k-1$ leaves correspond to unrooted binary subtrees in $T$ with $k$ leaves, namely, a subtree with a root $r'$ in $T_r$ gets the "parent" edge of $r'$ attached in $T$ (in particular, for $r'=r$, we get an extra leaf $\ell$ in the corresponding subtree of $T$).

The two recurrences need to be applied once for each vertex of $T_r$ in the bottom-up fashion, starting from the leaves of $T_r$ and ending at the root $r$.

P.S. Elements of valid partitions of $L(T)$ are studied to some extent in my paper under the name of $T$-consistent multicolors.

Case 2. $t(L)$ is an arbitrary subtree.

Smilarly to the above, we define $\ell$, $r$, and $T_v$.

For a vertex $v$ in $T_r$, define $$A_v(z)=a_1\cdot z+a_2\cdot z^2+\dots,$$ $$B_v(z)=b_1\cdot z+b_2\cdot z^2+\dots,$$ $$C_v(z)=c_1\cdot z+c_2\cdot z^2+\dots,$$ where

• $a_i$ is the number of forests in $T_v$, containing $v$ and consisting of $t(L_j)$, where $L_j$ ($j=1,2,\dots,i$) form an $i$-partition of $L(T_v)$ (notice that a subtree containing $v$ must also contain both its children in $T_v$ if there are any);

• $b_i$ is the number of forests in $T_v$, not containing $v$ and consisting of $t(L_j)$, where $L_j$ ($j=1,2,\dots,i$) form a partition of $L(T_v)$;

• $c_i$ is the number of forests in $T_v$, containing $v$ as a leaf and consisting of $t(L_1),\dots, t(L_{i-1})$ and $t(L_i\cup\{v\})$, where $L_j$ ($j=1,2,\dots,i$) form an $i$-partition of $L(T_v)$ (notice that a subtree containing $v$ must also contain exactly one child of $v$ in $T_v$).

If $v$ is a leaf then $A_v(z)=z$ and $B_v(z)=C_v(z)=0$.

If $u_1,u_2$ are the children of a non-leaf $v$, then $$\begin{cases} A_v(z) = \frac{1}{z}\cdot (A_{u_1}(z)+C_{u_1}(z))\cdot (A_{u_2}(z)+C_{u_2}(z)), \\ B_v(z) = (A_{u_1}(z)+B_{u_1}(z))\cdot (A_{u_2}(z)+B_{u_2}(z)), \\ C_v(z) = (A_{u_1}(z)+C_{u_1}(z))\cdot (A_{u_2}(z)+B_{u_2}(z))+(A_{u_1}(z)+B_{u_1}(z))\cdot (A_{u_2}(z)+C_{u_2}(z)). \end{cases}$$

The number of valid $k$-partitions of $T$ in given by the coefficient of $z^k$ in $$(1+z)\cdot A_r(z) + z\cdot B_r(z) + C_r(z).$$

Example. Let $T$ be a tree on 6 vertices $a,b,c,d,e,f$ with edges $(a,b)$, $(b,c)$, $(c,d)$, $(b,e)$, $(c,f)$. So the leaves of $T$ are $a,d,e,f$.

First we fix a leaf $\ell$, say, $\ell = a$. Then $r=b$ and we have a rooted tree $T_r$ with leaves $d,e,f$. For each of them we have $$(A_d(z),B_d(z),C_d(z)) = (A_e(z),B_e(z),C_e(z)) = (A_f(z),B_f(z),C_f(z)) = (z,0,0).$$

From ABC-values at $d,f$, we compute them at their parent $c$: $$(A_c(z),B_c(z),C_c(z)) = (z,z^2,2z^2).$$

From ABC-values at $c,e$, we compute them at their parent $r=b$: $$(A_r(z),B_r(z),C_r(z)) = (z+2z^2,z^2+z^3,2z^2+3z^3).$$

Now we compute the answer: $$(1+z)\cdot A_r(z) + z\cdot B_r(z) + C_r(z) = (1+z)\cdot (z+2z^2)+z\cdot (z^2+z^3)+(2z^2+3z^3)$$ $$=z+5z^2+6z^3+z^4.$$ It is easy to check that we indeed have one valid 1-parition of $L(T)$, five (equal number of edges in $T$) valid 2-partitions, six ($=\binom{4}{2}$) valid 3-partitions, and one valid 4-partition.

• Thank you for your answer ! You have convinced me that every binary subtree with $k$ leaves defines a valid $k$-partition, but I am struggling with the converse. Take a path of length 4 with vertices $a, b, c, d$ with leaves $a$, $b$. Then add a neighbor $e$ to $b$ and a neighbor $f$ to $c$. The $3$-partition $ad | e | f$ is valid, but I can't find a corresponding binary subtree. In fact, what I think would fit your description is the subtree induced by $\{e,b,c,f\}$, which has 2 leaves and is not binary. Do you think that the subtrees to cound need to be extended to be exact ? Jun 9 '15 at 20:26
• (erratum) The leaves of the path described above are $a, d$ and not $a, b$. Jun 9 '15 at 20:39
• @ManuelLafond: I understand $t(L)$ as a minimal binary subtree (as otherwise it does not make sense from the phylogenetic perspective). In these settings $ad|e|f$ is not a valid partition. Jun 9 '15 at 21:33
• Well, a non-binary $t(L)$ making sense or not depends on what you're doing I suppose. For my purposes, a valid partition (binary subtrees or not) means that the tree has a rooting that explains the trait corresponding to the partition without homoplasy - i.e. a value of the trait does not get inherited by two ancestors independently. Still, best answer so far...it gives me some hints on where to look for a lower bound. Jun 10 '15 at 14:40
• @ManuelLafond: I have addressed the case of arbitrary subtrees $t(L)$ in the update. Check it out. Jun 10 '15 at 21:58

ANSWER #2 (Feb. 9, 2016)

Nikita Alexeev and I have extended the approach that I outlined in the previous answer (case 2) to the case of phylogenetic networks, which resulted in the paper Combinatorial Scoring of Phylogenetic Networks.

Along the way, we have obtained a closed-form solution for the case of binary trees, and later discovered that this result was long known and first obtained by Steel (1992). This result (quoted in Theorem 1 in our paper) is the following.

The number of valid ("convex" in the terminology of the aforementioned papers) $k$-partitions $L(T)$ does not depend on the topology of a binary tree $T$ but only on the number of its leaves $n=|L(T)|$, and is given by the binomial coefficient: $$\binom{2n-k-1}{k-1}.$$ Correspondingly, the total number of valid partitions is the Fibonacci number: $$\sum_{k=1}^n \binom{2n-k-1}{k-1} = F_{2n-1}.$$

• Sounds great ! I'll definitely take a look at the paper. Feb 10 '16 at 15:03
• @ManuelLafond: Thanks for inspiration for this work! Also, if we learned the simple answer for binary trees right away, we would not probably bother with the generating functions technique, and the paper would never be written. Feb 10 '16 at 15:09