The $\ominus$-metric to compare phylogenetic networks

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 $\mathrm{P}=\mathrm{N}\mathrm{P}$. Although computing $d_{\ominus }^{-}$ is NP-hard in general, for distinct-cluster networks it reduces to $\text{textsc}VertexCover$, yielding a fixed-parameter algorithm and a polynomial-time $2$-approximation.