title: The comparison of tree-sibling time consistent phylogenetic networks is graph isomorphism-complete.
abstract: Several polynomial time computable metrics on the class of semibinary tree-sibling time consistent phylogenetic networks are available in the literature; 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, then the problem becomes much harder. More precisely, we prove 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 not to belong to P, 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.
authors: Department of Mathematics and Computer Science, University of the Balearic Islands, 07122 Palma de Mallorca, Spain.
authors: Gabriel
authors: 0000-0001-8845-4290
authors: G
authors: Cardona
authors: Department of Mathematics and Computer Science, University of the Balearic Islands, 07122 Palma de Mallorca, Spain.
authors: Mercè
authors: M
authors: Llabrés
authors: Department of Mathematics and Computer Science, University of the Balearic Islands, 07122 Palma de Mallorca, Spain.
authors: Francesc
authors: F
authors: Rosselló
authors: Algorithms, Bioinformatics, Complexity and Formal Methods Research Group, Technical University of Catalonia, 08034 Barcelona, Spain.
authors: Gabriel
authors: 0000-0001-9194-2703
authors: G
authors: Valiente
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D006801:Humans; D010802:Phylogeny