Abstract
Given a finite set X, a collection Tof rooted phylogenetic trees on Xand an integerk, theHybridization Numberproblem asks if there exists a phylogenetic network onXthat displays all trees fromTand has reticulation number at mostk. We show two kernelization algorithms forHybridization Number, with kernel sizes 4k(5k)tand 20k2(+−1)respectively, withtthe 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)t-time algorithm, with n =|X|and fsome computable function ofk.
Original language | English |
---|---|
Pages (from-to) | 1075-1089 |
Number of pages | 15 |
Journal | Journal of Computer and System Sciences |
Volume | 82 |
Issue number | 6 |
DOIs | |
Publication status | Published - 2016 |
Keywords
- Fixed-parameter tractability
- Kernelization
- Phylogenetic tree
- Phylogenetic network
- Hybridization number