← Back to Populations and Evolution
q-bio.PE

Why measuring evolutionary network similarity is computationally impossible

Peng Li, Zhiwei Liu, Yangjing Long

May 19, 2026

Evolutionary trees aren't always trees—they branch and reconnect when species hybridize or swap genes across distant lineages. Researchers proved that measuring the minimum changes needed to simplify any such network into an orderly "orchard" pattern is computationally intractable. This sets a hard limit on what evolutionary biologists can practically compute when reconstructing complex speciation histories.
Published as Computing the Arc-Deletion Distance to Orchard Networks is NP-hard arXiv:2605.19962
Read the original paper →