For binary phylogenetic trees, the study gives an exact recursive way to calculate the minimum number of cherry-picking sequences needed to reduce every subtree. It also shows that, with no restriction on sequence length, one sequence can reduce all non-trivial subtrees, and that the shortest such sequence has length equal to the number of unordered pairs of leaves.
The exact binary recursion
Alongside the ordinary covering number, the paper gives a second quantity called survival covering, built around subtrees that remain irreducible under the defined rules. For binary trees, its rules start by ordering the two child branches by leaf count. The smaller branch calls for a product when it has at least two leaves, an increase of one when it has one leaf, and a value of two in the cherry case. The ordinary covering number uses the product of the child survival-covering values in the first case, the larger child's survival-covering value when the smaller child has one leaf, and a value of one when a child has one leaf.
A separate result for non-binary trees
For non-binary trees, the survival value equals both the value for a transformed version of the tree called its caterpillarization and the maximum size of a set of pairwise survivably irreducible subtrees. At the root, the recursion multiplies the values of non-leaf children and adds the number of leaf children when non-leaf children are present; when every root child is a leaf, it uses the square of the leaf-child count. The paper states that this survival number can be computed in linear time for non-binary inputs.
Star trees and SubsetConnectivity
For star phylogenetic trees, deciding whether a bounded-size set of sequences covers all subtrees is equivalent to the defined SubsetConnectivity decision problem.
In that problem, let c(n) be the minimum complete-set size. When the label count increases from n to n+1, the paper proves that c(n+1) is either c(n) or c(n)+1. An exact set-cover computation reports c(n)=n-2 for the checked range of four through seven labels. That finite check does not establish the pattern for larger label counts.
The same recurrence has a conditional structural consequence: when the minimum complete-set size does not increase after one more label, every minimum complete set for the larger label count excludes labeled star trees.
Where the result stops
The ordinary covering number for general non-binary trees remains unresolved, with only loose bounds reported even for star inputs.
The appendix reports that some orchard and tree-child network inputs have non-finite covering numbers because some allowed subtrees cannot be reduced by any corresponding sequence. These examples do not characterize every network in either class, so they do not establish that all such networks have non-finite covering numbers.
No empirical sample was analyzed. The work concerns formal trees, networks, subtrees and sequences, using constructive proofs and recursive arguments, plus a finite-range exact set-cover computation.
Paper data and sources
Original title: How many cherry-picking sequences are needed to reduce all subtrees of a phylogenetic tree?
Authors: Bálint Kollmann, Yukihiro Murakami, Takatora Suzuki
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text