Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
429757 | Journal of Computer and System Sciences | 2016 | 15 Pages |
•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.