The sliding cubes model serves as a well-established theoretical framework for formalizing and analyzing reconfiguration algorithms in modular robotic systems built from face-connected cubic modules. We extend the parallel sliding cubes model from two to three dimensions, presenting new algorithms, surprising complexity results, and a generalization of the best known bounds from two to three dimensions. A companion video visualizes and explains our results.

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).

In the classic sliding cube model for programmable matter in three dimensions, the task is to find a reconfiguration sequence between two connected configurations of n indistinguishable unit cube modules by sliding modules along their neighbors' faces. Depending on the objective, this sequence should minimize either the total energy expended (the number of moves) or the total elapsed time (the makespan). We give a number of results for the three-dimensional setting, including (i) the first algorithm that achieves worst-case optimal makespan under parallel motion in three dimensions, (ii) a proof of log-APX-hardness to decide either the optimal makespan or the optimal number of moves, which is the strongest known inapproximability bound in any related model, and (iii) a proof of NP-hardness to decide the optimal makespan under parallel motion, even if the two configurations differ only by one module and the optimal makespan is at most two. Our results strengthen the inapproximability claim from [Hugo A. Akitaya et al., 2022] and answer a question of [Akitaya et al., 2025] in the negative.

We study the reconfiguration of odd matchings of combinatorial graphs. Odd matchings are matchings that cover all but one vertex of a graph. A reconfiguration step, or flip, is an operation that matches the isolated vertex and, consequently, isolates another vertex. The flip graph of odd matchings is a graph that has all odd matchings of a graph as vertices and an edge between two vertices if their corresponding matchings can be transformed into one another via a single flip. We show that computing the diameter of the flip graph of odd matchings is Π₂^p-hard. This complements a recent result by Wulf [FOCS25] that it is Π₂^p-hard to compute the diameter of the flip graph of perfect matchings where a flip swaps matching edges along a single cycle of unbounded size. Further, we show that computing the radius of the flip graph of odd matchings is Σ₃^p-hard. The respective decision problems for the diameter and the radius are also complete in the respective level of the polynomial hierarchy. This shows that computing the radius of the flip graph of odd matchings is provably harder than computing its diameter, unless the polynomial hierarchy collapses. Finally, we reduce set cover to the problem of finding shortest flip sequences. As a consequence, we show APX-hardness and that the problem cannot be approximated by a sublogarithmic factor. By doing so, we answer a question asked by Aichholzer, Brenner, Dorfer, Hoang, Perz, Rieck, and Verciani [GD25].

We study the problem of reconfiguring odd matchings, that is, matchings that cover all but a single vertex. Our reconfiguration operation is a so-called flip where the unmatched vertex of the first matching gets matched, while consequently another vertex becomes unmatched. We consider two distinct settings: the geometric setting, in which the vertices are points embedded in the plane and all occurring odd matchings are crossing-free, and a combinatorial setting, in which we consider odd matchings in general graphs. For the latter setting, we provide a complete polynomial time checkable characterization of graphs in which any two odd matchings can be reconfigured into each another. This complements the previously known result that the flip graph is always connected in the geometric setting [Oswin Aichholzer et al., 2025]. In the combinatorial setting, we prove that the diameter of the flip graph, if connected, is linear in the number of vertices. Furthermore, we establish that deciding whether there exists a flip sequence of length k transforming one given matching into another is NP-complete in both the combinatorial and the geometric settings. To prove the latter, we introduce a framework that allows us to transform partial order types into general position with only polynomial overhead. Finally, we demonstrate that when parameterized by the flip distance k, the problem is fixed-parameter tractable (FPT) in the geometric setting when restricted to convex point sets.

A flip in a plane spanning tree T is the operation of removing one edge from T and adding another edge such that the resulting structure is again a plane spanning tree. For trees on a set of points in convex position we study two classic types of constrained flips: (1) Compatible flips are flips in which the removed and inserted edge do not cross each other. We relevantly improve the previous upper bound of 2n-O(√n) on the diameter of the compatible flip graph to (5n/3)-O(1), by this matching the upper bound for unrestricted flips by Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber [SODA 2025] up to an additive constant of 1. We further show that no shortest compatible flip sequence removes an edge that is already in its target position. Using this so-called happy edge property, we derive a fixed-parameter tractable algorithm to compute the shortest compatible flip sequence between two given trees. (2) Rotations are flips in which the removed and inserted edge share a common vertex. Besides showing that the happy edge property does not hold for rotations, we improve the previous upper bound of 2n-O(1) for the diameter of the rotation graph to (7n/4)-O(1).