Deciding the existence of a cherry-picking sequence is hard on two trees

DOI10.1016/j.dam.2019.01.031zbMath1409.05191arXiv1712.02965MaRDI QIDQ1741507

Steven Kelk, Leo van Iersel, Simone Linz, Janosch Döcker

Publication date: 3 May 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1712.02965

zbMATH Keywords

satisfiability; NP-hardness; phylogenetic networks; phylogenetics; temporal networks; elimination orders

Mathematics Subject Classification ID

92D15: Problems related to evolution

05C90: Applications of graph theory

05C82: Small world graphs, complex networks (graph-theoretic aspects)

92B10: Taxonomy, cladistics, statistics in mathematical biology

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Uses Software

• HybridNET
• PhyloNetwork