Kernelizations for the hybridization number problem on multiple nonbinary trees

• We study constructing a network displaying a given collection of phylogenetic trees.
• Our kernelization techniques work for inputs consisting of multiple binary trees.
• Previous results were restricted to two trees and/or binary trees.
• A unified and simplified approach for dealing with common chains of nonbinary trees.
• Polynomial-time solvability with fixed number of reticulations.

Given a finite set X  , a collection TT of rooted phylogenetic trees on X and an integer k, the Hybridization Number problem asks if there exists a phylogenetic network on X   that displays all trees from TT and has reticulation number at most k. We show two kernelization algorithms for Hybridization Number, with kernel sizes 4k(5k)t4k(5k)t and 20k2(Δ+−1)20k2(Δ+−1) respectively, with t   the number of input trees and Δ+Δ+ their maximum outdegree. Experiments on simulated data demonstrate the practical relevance of our kernelization algorithms. In addition, we present an nf(k)tnf(k)t-time algorithm, with n=|X|n=|X| and f some computable function of k.