The Reeb graph edit distance is universal (Q2052722)

For a Morse function $f: X\to \mathbb R$ on a compact smooth manifold, the Reeb graph of $f$ is the quotient space $X/\sim_f$, with $x\sim_f$ $y$ iff $x$ and $y$ belong to the same connected component of some level set $f^{-1}(t)$ for some real number $t$. It is proved in Proposition 2 that any Reeb graph of a PL (piece-wise linear) function is a finite topological graph. In Section 3, the authors define some pseudo-metrics on the collection of the Reeb graphs for all the Morse functions (or PL functions) on a fixed space $X$. The authors define the universal properties of a pseudo-metric. They construct a distance $d_U$ and prove that it is universal in Proposition 5. They prove that $d_U$ is intrinsic in Proposition 6 and state that whether $d_U$ is a geodesic metric is unknown. They also review and re-introduce the functional distortion distance and the interleaving distance and claim that these two distances are stable but not universal. Finally, they give some lower bounds. In Section 4, the authors introduce a new distance, the edit distance $d_e$. They prove that $d_e$ is stable and universal. In Section 5, the authors further explore the edit distance of Reeb graphs $d_{eGraph}$ as well as its stability and universality. In Section 6, the authors discuss the motivation of the study of $d_U$, $d_e$, and $d_{eGraph}$ in topological data analysis, the relations between these distances and graph zigzagging, and some further questions which are of interest and could motivate further research.