We consider the problem of reconfiguring non-crossing spanning trees on point sets. For a set P of n points in general position in the plane, the flip graph ℱ(P) has a vertex for each non-crossing spanning tree on P and an edge between any two spanning trees that can be transformed into each other by the exchange of a single edge (coined a flip). This flip graph has been intensively studied, lately with an emphasis on determining its diameter diam(ℱ(P)) for sets P of n points in convex position. For this case, the current best bounds are 14/9⋅n - O(1) ≤ diam(ℱ(P)) < 15/9⋅n - 3, obtained in a recent breakthrough work [Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber; SODA 2025]. The crucial tool for both the upper and lower bound are so-called conflict graphs, which the authors stated might be the key ingredient for determining the diameter (up to lower-order terms). In this paper, we pick up the concept of conflict graphs from the above-mentioned work and show that this tool is even more versatile than previously hoped. As our first main result, we use conflict graphs to show that computing the flip distance between two non-crossing spanning trees is NP-hard, even for point sets in convex position. Interestingly, the result still holds for more constrained flip operations, concretely, compatible flips (where the removed and the added edge do not cross) and rotations (where the removed and the added edge share an endpoint). Additionally, we present new insights on the diameter of the flip graph, by this directly extending the line of research from [BKUV SODA25]. Their lower bound is based on a constant-size pair of trees, one of which is of a type we refer to as stacked. We show that if one of the trees is stacked, then the lower bound is indeed optimal up to a constant term, that is, there exists a flip sequence of length at most 14/9⋅(n-1) to any other tree. Lastly, we improve the lower bound on the diameter of the flip graph ℱ(P) for n points in convex position to 11/7⋅n-o(n).

Abstract Recently, p -presentation distances for $$p\in [1,\infty ]$$ p ∈ [ 1 , ∞ ] were introduced for merge trees and multiparameter persistence modules as more sensitive variations of the respective interleaving distances ( $$p=\infty )$$ p = ∞ ) . It is well-known that computing the interleaving distance is NP-hard in both cases. We extend this result by showing that computing the p -presentation distance is NP-hard for all $$p\in [1,\infty )$$ p ∈ [ 1 , ∞ ) for both merge trees and t -parameter persistence modules for any $$t\ge 2$$ t ≥ 2 . Though the details differ, both proofs follow the same novel strategy, suggesting that our approach can be adapted to proving the NP-hardness of other distances based on sums or p -norms.

For a set P of n points in general position in the plane, the flip graph F (P ) has a vertex for each noncrossing spanning tree on P and an edge between any two spanning trees that can be transformed into each other by one edge flip, i.e., the deletion and addition of exactly one edge. The diameter diam(F (P )) of this flip graph is subject of intensive study. For points P in general position, it is between and 2n - 4, with no improvement for 25 years. For points P in convex position, diam(F (P )) lies between and ≈ 1.95n, where the lower bound was conjectured to be tight up to an additive constant and the upper bound is a very recent breakthrough improvement over several previous bounds of the form 2n - o (n ).

We establish bi-Lipschitz bounds certifying quasi-universality (universality up to a constant factor) for various distances between Reeb graphs: the interleaving distance, the functional distortion distance, and the functional contortion distance. The definition of the latter distance is a novel contribution, and for the special case of contour trees we also prove strict universality of this distance. Furthermore, we prove that for the special case of merge trees the functional contortion distance coincides with the interleaving distance, yielding universality of all four distances in this case.

Abstract The algebraic stability theorem for persistence modules is a central result in the theory of stability for persistent homology. We introduce a new proof technique which we use to prove a stability theorem for n-dimensional rectangle decomposable persistence modules up to a constant $$2n-1$$ 2 n - 1 that generalizes the algebraic stability theorem, and give an example showing that the bound cannot be improved for $$n=2$$ n = 2 . We then apply the technique to prove stability for block decomposable modules, from which novel results for zigzag modules and Reeb graphs follow. These results are improvements on weaker bounds in previous work, and the bounds we obtain are optimal.

The interleaving distance is arguably the most prominent distance measure in topological data analysis. In this paper, we provide bounds on the computational complexity of determining the interleaving distance in several settings. We show that the interleaving distance is NP-hard to compute for persistence modules valued in the category of vector spaces. In the specific setting of multidimensional persistent homology we show that the problem is at least as hard as a matrix invertibility problem. Furthermore, this allows us to conclude that the interleaving distance of interval decomposable modules depends on the characteristic of the field. Persistence modules valued in the category of sets are also studied. As a corollary, we obtain that the isomorphism problem for Reeb graphs is graph isomorphism complete.