2026/07/09 by Marc Hellmuth, Manuel Lafond, Guillaume E. Scholz · 1 voice
Computer Science · #cs.DM
We introduce two novel distances for comparing rooted phylogenetic networks based on the \ominus-operator, which removes a vertex while preserving the ancestor relations among the remaining vertices. The distance d\ominus measures the minimum number of such removals needed to obtain isomorphic networks, whereas d\ominus- ignores shortcut arcs and therefore compares the induced ancestry structures. We show that d\ominus is a metric up to leaf-fixing isomorphism and that d\ominus- is a metric up to shortcut-free isomorphism. Moreover, both distances extend the Robinson--Foulds distance on phylogenetic trees and are bounded below by the hardwired cluster distances. For several broad network classes, including tree-child, normal, level-1, and regular networks, d\ominus- can be computed in polynomial time. In contrast, computing d\ominus is NP-hard, W[2]-hard when parameterized by the distance value, and admits no polynomial-time constant-factor approximation unless P=NP. Although computing d\ominus- is NP-hard in general, for distinct-cluster networks it reduces to Vertex Cover, yielding a fixed-parameter algorithm and a polynomial-time 2-approximation.