A graph-matching formulation of the interleaving distance between merge trees

In this work, we studied the interleaving distance between merge trees from a combinatorial point of view. In the first part of the paper, we used a particular type of matching between trees to obtain a novel formulation of the distance. This formulation unveiled a link connecting the interleaving distance and edit distances between merge trees, which was of great interest due to the recursive decomposition properties and constrained formulations with polynomial time algorithms that these distances often enjoyed. In the second part of the paper, we built on this connection by applying tools from edit distances to obtain a constrained formulation of the interleaving distance and a recursive procedure which allowed us to find algorithms for upper and lower bounds of the interleaving distance. We implemented those algorithms and used them to test another upper bound presented by other authors, and tackled some simulations and case studies. Motivated by the literature on edit distances, we believe that our novel formulation could lead to novel heuristics to compute the interleaving distance and that applying our recursive scheme to the constrained interleaving distance would produce polynomial time upper bounds of practical relevance.