تقرير
Agreement forests of caterpillar trees: complexity, kernelization and branching
| العنوان: | Agreement forests of caterpillar trees: complexity, kernelization and branching |
|---|---|
| المؤلفون: | Kelk, Steven, Meuwese, Ruben |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics Quantitative Biology |
| مصطلحات موضوعية: | Quantitative Biology - Populations and Evolution, Computer Science - Data Structures and Algorithms, Mathematics - Combinatorics |
| الوصف: | Given a set $X$ of species, a phylogenetic tree is an unrooted binary tree whose leaves are bijectively labelled by $X$. Such trees can be used to show the way species evolve over time. One way of understanding how topologically different two phylogenetic trees are, is to construct a minimum-size agreement forest: a partition of $X$ into the smallest number of blocks, such that the blocks induce homeomorphic, non-overlapping subtrees in both trees. This comparison yields insight into commonalities and differences in the evolution of $X$ across the two trees. Computing a smallest agreement forest is NP-hard (Hein, Jiang, Wang and Zhang, Discrete Applied Mathematics 71(1-3), 1996). In this work we study the problem on caterpillars, which are path-like phylogenetic trees. We will demonstrate that, even if we restrict the input to this highly restricted subclass, the problem remains NP-hard and is in fact APX-hard. Furthermore we show that for caterpillars two standard reductions rules well known in the literature yield a tight kernel of size at most $7k$, compared to $15k$ for general trees (Kelk and Simone, SIAM Journal on Discrete Mathematics 33(3), 2019). Finally we demonstrate that we can determine if two caterpillars have an agreement forest with at most $k$ blocks in $O^*(2.49^k)$ time, compared to $O^*(3^k)$ for general trees (Chen, Fan and Sze, Theoretical Computater Science 562, 2015), where $O^*(.)$ suppresses polynomial factors. Comment: 33 pages, 15 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2307.12176 |
| رقم الأكسشن: | edsarx.2307.12176 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |