2009/02/26 by Gabriel Cardona, Mercè Llabrés, Cardona, Gabriel +7
Biochemistry, Genetics and Molecular Biology · Computer Science · Earth and Planetary Sciences · #Discrete Mathematics (cs.DM) #Evolution and Paleontology Studies #FOS: Biological sciences #FOS: Computer and information sciences #Genetic diversity and population structure #Genomics and Phylogenetic Studies #Populations and Evolution (q-bio.PE) #cs.DM #q-bio.PE
paper · pdf · doi:10.48550/arxiv.0902.4640
10 pages, 3 figures
arxiv created 2009/02/26 · openalex publication_date 2009/02/26 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a previous work, we gave a metric on the class of semibinary tree-sibling time consistent phylogenetic networks that is computable in polynomial time; in particular, the problem of deciding if two networks of this kind are isomorphic is in P. In this paper, we show that if we remove the semibinarity condition above, then the problem becomes much harder. More precisely, we proof that the isomorphism problem for generic tree-sibling time consistent phylogenetic networks is polynomially equivalent to the graph isomorphism problem. Since the latter is believed to be neither in P nor NP-complete, the chances are that it is impossible to define a metric on the class of all tree-sibling time consistent phylogenetic networks that can be computed in polynomial time.