A kernel for the maximum agreement forest problem on multiple binary phylogenetic trees
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918399678873600 |
|---|---|
| author | Kelk, Steven Meuwese, Ruben van Iersel, Leo |
| author_facet | Kelk, Steven Meuwese, Ruben van Iersel, Leo |
| contents | The maximum agreement forest (MAF) problem in phylogenetics takes as input a set t >= 2 of binary phylogenetic trees T on the same set of taxa X. It asks for a partition of X into the smallest number of blocks such that the subtrees induced by these blocks are disjoint and have common topology across all the trees in T. We produce a modified version of the well-known chain reduction rule in order to prove that after exhaustive application of reduction rules each tree has O( t * r * k ) leaves, where k is the natural parameter (the number of blocks) and r=min{max{k,3},t+1}}. We prove this bound for both the unrooted and rooted version of the problem, and demonstrate that the bound r, the length to which common chains are truncated, is tight. Our results constitute the first kernels for MAF in the t>2 regime. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_22281 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A kernel for the maximum agreement forest problem on multiple binary phylogenetic trees Kelk, Steven Meuwese, Ruben van Iersel, Leo Combinatorics Populations and Evolution The maximum agreement forest (MAF) problem in phylogenetics takes as input a set t >= 2 of binary phylogenetic trees T on the same set of taxa X. It asks for a partition of X into the smallest number of blocks such that the subtrees induced by these blocks are disjoint and have common topology across all the trees in T. We produce a modified version of the well-known chain reduction rule in order to prove that after exhaustive application of reduction rules each tree has O( t * r * k ) leaves, where k is the natural parameter (the number of blocks) and r=min{max{k,3},t+1}}. We prove this bound for both the unrooted and rooted version of the problem, and demonstrate that the bound r, the length to which common chains are truncated, is tight. Our results constitute the first kernels for MAF in the t>2 regime. |
| title | A kernel for the maximum agreement forest problem on multiple binary phylogenetic trees |
| topic | Combinatorics Populations and Evolution |
| url | https://arxiv.org/abs/2602.22281 |