Flip Distance of Non-Crossing Spanning Trees:
NP-Hardness and Improved Bounds

Non-crossing configurations such as triangulations, spanning trees, matchings, or polygonizations on planar point sets are fundamental structures in computational geometry, with wide applications. In dynamic environments or interactive settings, it is often necessary to transform one configuration into another through a sequence of local modifications, while ensuring that the non-crossing property is preserved at every step and that the intermediate configurations are of the same type. This process, known as (discrete) reconfiguration, raises natural algorithmic questions: Given two non-crossing configurations, is it possible to convert one into the other using only basic operations? If so, it is of interest to bound the length of a shortest reconfiguration sequence between any two configurations, to compute the length of an optimal sequence between two given configurations, and to efficiently determine a short(est) sequence.

These questions can be nicely rephrased in terms of a so-called flip graph. The flip graph of a discrete reconfiguration problem has a vertex for each configuration and an edge between any two configurations that can be transformed into one another by a single basic discrete operation, called a flip. In terms of the flip graph, the above-mentioned three questions then read as follows: Is the flip graph connected? What is the diameter of the flip graph? Can a shortest path (flip sequence) between two vertices of the flip graph be computed efficiently?

For many types of geometric graphs, the most classical flip operation is the exchange of one edge with another edge, see also Figure 1. For instance, it is known that the flip graph of triangulations on a set of $n$ points in the plane in convex position [31] and has diameter exactly $2n-10$ [36, 35]. For decades, it has been a tantalizing and important open problem in theoretical computer science whether a shortest flip sequence between two triangulations of a convex point set can be computed in polynomial time. This problem is equivalent to the complexity of computing the rotation distance between two rooted binary trees.

In this work, we consider flips between non-crossing geometric spanning trees. Let $P$ denote a set of $n$ points in the plane in general position, that is, no three points of $P$ are collinear. A non-crossing spanning tree on $P$ is a spanning tree that has $P$ as its vertex set and whose edges are pairwise non-crossing straight-line segments. A flip in a non-crossing spanning tree $T$ on $P$ is the exchange of one edge of $T$ by a different one such that the resulting graph is again a non-crossing spanning tree $T^{\prime }$ on $P$; see Figure 1 for an example. The according flip graph $ℱ(P)$ has a vertex for each non-crossing spanning tree on $P$ and an edge between any two trees whenever they can be transformed into each other by a single edge flip. For two trees $T$ and $T^{\prime }$ on $P$, we denote their flip distance, the length of a shortest path between $T$ and $T^{\prime }$ in $ℱ(P)$, by $\mathrm{dist}(T,T^{\prime })$.

In 1996, Avis and Fukuda [10] showed in their famous reverse search paper that $ℱ(P)$ is connected for any $n$-point set $P$ in general position, and that its radius is bounded from above by $n-2$, implying $\mathrm{diam}(ℱ(P))\le 2n-4$. In 1999, Hernando, Hurtado, Márquez, Mora, and Noy [25] showed that for convex $n$-point sets $P$, it holds that $\mathrm{diam}(ℱ(P))\ge \lfloor 3/2\cdot n\rfloor -5$. Since then, the flip graph $ℱ(P)$ of non-crossing geometric spanning trees on point sets $P$ in convex position has been subject of intensive study; see the discussion in Section 1.1 below for some details. For a long time, it was conjectured that the true value for its diameter should be $3/2\cdot n+c$ for some constant $c$. Very recently, Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber [13] refuted this conjecture by obtaining the currently best known bounds of $14/9\cdot n+O(1)\le \mathrm{diam}(ℱ(P))\le 15/9\cdot n-O(1)$ for the diameter of the flip graph on non-crossing spanning trees on point sets in convex position. The crucial tool for both the upper and lower bound are so-called conflict graphs, which the authors introduced and stated might be the key ingredient for determining the diameter of the flip graph of spanning trees for point sets in convex position (up to lower-order terms). Their lower bound is based on a constant-size example containing a tree belonging to a family of trees that we call stacked.

In this work, we pick up the concept of conflict graphs from [13] and show that this tool is even more versatile than previously hoped. We prove that the flip distance between two trees can be as high as $11/7\cdot n-o(n)$, by this directly extending the line of research from [13].

We further show that if one of the trees is stacked, then the lower bound from [13] is indeed the best possible. In other words, whenever one of the trees is stacked, then there exists a flip sequence of length at most $14/9\cdot n-O(1)$ to any other tree.

Moreover, we use conflict graphs beyond the expectations of [13], showing that they can also be used to prove that computing the flip distance between two non-crossing spanning trees is $\mathrm{𝖭𝖯}$-hard, even for point sets in convex position.

Interestingly, this 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). In Figure 1, while the first flip is just an edge exchange, the second flip a compatible flip, and the third flip is a rotation.

We point out that the latter two statements constitute the first hardness results for flip graphs on point sets in convex position. Moreover, Theorem 4 refutes the long-held belief that the flip distance can be computed in polynomial time when the so-called happy edge property holds, because that property holds for compatible flips of non-crossing spanning trees on convex point sets. See Section 1.1 for more background and Table 1 for an overview of complexity status for various flip graphs of non-crossing structures on point sets.

Our results build on insights from Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber [13]. In the following, we introduce some of their concepts.

In this section we sketch proofs for our hardness results. Theorem 3 states that the decision problem of whether there exists a flip sequence of length at most $\delta$ between two non-crossing spanning trees $T,T^{\prime }$ is $\mathrm{𝖭𝖯}$-complete. In fact, this holds even for point sets in convex position. Our proof of Theorem 3 goes via an intermediate problem. Specifically, we show that it is $\mathrm{𝖭𝖯}$-complete to decide whether a directed graph $H$ has an acyclic subset of size at least $k$, even if $H$ is the conflict graph of two non-crossing trees with a given linear representation.

Our proof of Proposition 8 is a reduction from the $\mathrm{𝖭𝖯}$-complete problem Planar Max-2SAT. We consider a restricted version [17], in which we are given a 2SAT-formula $\varphi$ with variable-set $X$ and clause-set $𝒞$ whose vertex-clause incidence graph $G_{\varphi }$ admits an aligned drawing, namely, a drawing with all variables on a horizontal line $L$ and no edge crossing $L$ or any other edge. In particular, every clause lies either in the upper or lower halfplane defined by $L$. Additionally given an integer $t$, Planar Max-2SAT asks whether $X$ admits a truth assignment such that at least $t$ clauses in $𝒞$ are satisfied.

For fixed $\varphi$ and $t$, we construct two non-crossing trees $T,T^{\prime }$ with a linear representation and an integer $k$ such that the following are equivalent:

• $\mathrm{■}$

  The conflict graph $H=H(T,T^{\prime })$ admits an acyclic subset of size at least $k$.

• $\mathrm{■}$

  The 2SAT-formula $\varphi$ admits a truth assignment that satisfies at least $t$ clauses.

To construct $T$ and $T^{\prime }$, we model the variables and clauses in $\varphi$ with small gadgets. In doing so, we also discuss the conflicts that occur. Recall that each gap has a type: above, below, or crossing. In fact, it will be enough for us to focus on the mixed conflicts, i.e., those between gaps of different types. We also remark that our construction only has conflicts $\overrightarrow{g_i{g}_j}$ of type 1, i.e., where $e_i$ properly crosses $e_j^{\prime }$ as illustrated in Figure 4(a).

Let $x\in X$ be a variable and $d=\mathrm{deg}(x)$ be its degree in $G_{\varphi }$, i.e., $x$ occurs (negated or non-negated) in exactly $d$ clauses. The variable-gadget for $x$ consists of $8d+1$ pairs of edges, of which $6d$ are near-near pairs and hence their corresponding $6d$ gaps are vertices in the conflict graph $H=H(T,T^{\prime })$. The gadget is illustrated in Figure 5(a) and the corresponding mixed conflicts in Figure 5(b). The $6d$ gaps form a path $P$ of double conflicts in the conflict graph $H$, i.e., every acyclic subset is an independent set in $P$. We partition $P$ into two independent sets $t(x)$ and $f(x)$ by alternating the gaps in $t(x)$ and $f(x)$ along $P$. Later we ensure that every acyclic subset $S$ of $H$ with $|S|\ge k$ either contains all of $t(x)$ or all of $f(x)$, which encodes the two possible truth assignments True and False for variable $x$.

We place each variable-gadget at the position of the corresponding variable in the aligned drawing of $G_{\varphi }$ in such a way that the rightmost point of any gadget coincides with the leftmost point of the next gadget (immediately to the right). Secondly, for each clause $C$ with incident variables $x$ and $y$ we introduce a new gap $g_x$ in the variable-gadget of $x$ and a new gap $g_y$ in the variable-gadget of $y$. For each $z\in \{x,y\}$, the edge pair for $g_z$ has an edge of length $3$ in the variable-gadget of $z$ and an edge connecting the gadgets of $x$ and $y$. See Figures 6(a) and 7(a) for an illustration. To ensure that different clause-gadgets do not cross, long edges are put in the halfplane that contains the clause $C$ in the aligned drawing of $G_{\varphi }$. Further, the position of $g_z$ on the path $P$ of length $6\mathrm{deg}(z)$ in the variable-gadget of $z$ is chosen with respect to the order of incident edges at $z$ in the drawing of $G_{\varphi }$.

Moreover, $g_z$ is chosen such that it has a double conflict with a gap in $t(z)$ if $z$ appears negated in $C$, and a double conflict with a gap in $f(z)$ if $z$ appears non-negated in $C$. This ensures that an acyclic set $S$ contains the gap $g_z$ only if the truth assignment of variable $z$ satisfies the clause $C$. A double conflict between the two gaps $g_x,g_y$ of the clause-gadget ensures that at most one of $g_x,g_y$ is in any acyclic set $S$. There are six further mixed conflicts between $g_x,g_y$ and the variable-gaps, as illustrated in Figures 6(b) and 7(b). Given a truth assignment, we choose all of $t(x)$ when $x$ is True, $f(x)$ when $x$ is False, and one gap $g_z$ in each satisfied clause. That this gives an acyclic subset $S$ of $H(T,T^{\prime })$, relies on the following observation.

In fact, each of the sets $A$, $B$, $C$ of all above, all below, and all crossing gaps, respectively, is acyclic by Lemma 6. Thus with Observation 9 it follows that every set $S\subseteq V(H)$ with no double conflict and none of the exceptional conflicts in Observation 9 is acyclic by taking first $A\cap S$, then $C\cap S$, and finally $B\cap S$ for a topological ordering.

This way, every truth assignment satisfying $t$ of $\varphi$ corresponds to an acyclic set $S\subseteq V(H)$ containing exactly half of all variable-gaps and exactly $t$ of all clause-gaps. Finally, for the other direction (getting a truth assignment from an acyclic subset $S$), we need to ensure that for every variable $x$ we have $t(x)\subseteq S$ or $f(x)\subseteq S$, as long as $S$ is large enough. To this end, let $m=|𝒞|$ and for each variable-gadget we apply an $m$-blowup to the first and last gap, a $2m$-blowup to all other variable-gaps, while applying no blowup to the clause-gaps. See Figure 8 for an illustration. Setting $k=m(12m+6-|X|)+t$ concludes our reduction from Planar Max-2SAT and thus the proof of Proposition 8.

In order to finally prove Theorem 3, we now reduce the problem of finding large acyclic subsets in conflict graphs to the problem of finding short flip sequences in $\beta$-blowups.

In this section, we improve the upper bound for the special case where in one of the two trees, the (relevant) edges can be partitioned into independent “stacks” of nested edges. This can be seen as a first natural generalization of an upper bound where one tree is a separated caterpillar, that is, a tree with two stacks [13, Section 6, arXiv-Version]. Further, the top tree in the best previously known lower bound example in [13], depicted in Figure 9, has this property. Throughout this section, we refer to a non-crossing spanning tree on a convex point set in linear representation simply as a tree.

We call a tree $T$ stacked if its edge set can be partitioned into sets $S_1,\mathrm{\dots },S_k$ such that

1. (i)

   no edge in $S_i$ covers an edge in $S_j$ for $i\ne j$, and

2. (ii)

   each $S_i$ is totally ordered by the covering relation.

Let $T^{\prime }$ be another tree on the same vertex set. We say that $T$ is stacked with respect to $T^{\prime }$ if the subset $N$ of edges in $T$ that are in near-near pairs of $(T,T^{\prime })$ admits a partition into sets $S_1,\mathrm{\dots },S_k$ satisfying properties (i) and (ii). Note that if $T$ is stacked then it is stacked with respect to any $T^{\prime }$. We refer to the edge sets $S_i$ as stacks (with respect to $T^{\prime }$).

We construct trees $T^i$ and ${\tilde{T}}^i$ iteratively, and show that their conflict graph has $7i$ vertices and a largest acyclic subset of size at most $3i+1$. The latter divided by the former tends to $3/7$, which allows us to use Theorem 5 (ii) to prove $\mathrm{diam}({ℱ}_n)\ge 11/7\cdot n-o(n)$.

We start with the trees $T^1$ and ${\tilde{T}}^1$ illustrated in Figure 11. These are trees on vertices $v_1,\mathrm{\dots },v_8,x,y,v_9$ labeled from left to right along the spine and have short edges $v_2{v}_3$, $v_6{v}_7$ and $xy$ as well as edges $e_i$ and ${\tilde{e}}_i$ for $i=1,\mathrm{\dots },7$, respectively.

Next, we construct $T^{\mathrm{\ell }}$ and ${\tilde{T}}^{\mathrm{\ell }}$ inductively for $\mathrm{\ell }\ge 2$. Assume that $T^{\mathrm{\ell }-1}$ and ${\tilde{T}}^{\mathrm{\ell }-1}$ are given. Add vertices $v_1^{\mathrm{\ell }},\mathrm{\dots },v_5^{\mathrm{\ell }}$ from left to right to the left of $v_1^{\mathrm{\ell }-1}$ and let $v_6^{\mathrm{\ell }}=v_2^{\mathrm{\ell }-1}$. Further, add a vertex $v_7^{\mathrm{\ell }}$ between $v_3^{\mathrm{\ell }-1}$ and $v_4^{\mathrm{\ell }-1}$, a vertex $v_8^{\mathrm{\ell }}$ between $v_8^{\mathrm{\ell }-1}$ and $x$, and a vertex $v_9^{\mathrm{\ell }}$ to the right of $v_9^{\mathrm{\ell }-1}$. For an illustration consider Figure 12.

The edges in $T^{\mathrm{\ell }-1}$ and ${\tilde{T}}^{\mathrm{\ell }-1}$ are also present in $T^{\mathrm{\ell }}$ and ${\tilde{T}}^{\mathrm{\ell }}$, respectively, except that the right endpoint of $e_4^{\mathrm{\ell }-1}$ and $e_6^{\mathrm{\ell }-1}$ (which was $x$) is changed to $v_8^{\mathrm{\ell }}$, and the left endpoint of ${\tilde{e}}_2^{\mathrm{\ell }-1}$ and ${\tilde{e}}_7^{\mathrm{\ell }-1}$ (which was $v_3^{\mathrm{\ell }-1}$) is changed to $v_7^{\mathrm{\ell }}$. Correspondingly, we change $g_2^{\mathrm{\ell }-1}$ to $v_7^{\mathrm{\ell }}{v}_4^{\mathrm{\ell }-1}$ and $g_6^{\mathrm{\ell }-1}$ to $v_8^{\mathrm{\ell }-1}{v}_8^{\mathrm{\ell }}$. We put a short edge $v_2^{\mathrm{\ell }}{v}_3^{\mathrm{\ell }}$ in both $T^{\mathrm{\ell }}$ and ${\tilde{T}}^{\mathrm{\ell }}$. Lastly, we add the following edges to $T^{\mathrm{\ell }}$ and ${\tilde{T}}^{\mathrm{\ell }}$
$e_1^{\mathrm{\ell }}=v_1^{\mathrm{\ell }}{v}_5^{\mathrm{\ell }},e_2^{\mathrm{\ell }}=v_2^{\mathrm{\ell }}{v}_4^{\mathrm{\ell }},e_3^{\mathrm{\ell }}=v_2^{\mathrm{\ell }}{v}_5^{\mathrm{\ell }},e_4^{\mathrm{\ell }}=v_5^{\mathrm{\ell }}x,e_5^{\mathrm{\ell }}=v_6^{\mathrm{\ell }}{v}_7^{\mathrm{\ell }},e_6^{\mathrm{\ell }}=v_1^{\mathrm{\ell }-1}x,e_7^{\mathrm{\ell }}=x{v}_9^{\mathrm{\ell }},$ ${\tilde{e}}_1^{\mathrm{\ell }}=v_1^{\mathrm{\ell }}{v}_3^{\mathrm{\ell }},{\tilde{e}}_2^{\mathrm{\ell }}=v_3^{\mathrm{\ell }}{v}_9^{\mathrm{\ell }-1},{\tilde{e}}_3^{\mathrm{\ell }}=v_4^{\mathrm{\ell }}{v}_3^{\mathrm{\ell }-1},{\tilde{e}}_4^{\mathrm{\ell }}=v_5^{\mathrm{\ell }}{v}_3^{\mathrm{\ell }-1},{\tilde{e}}_5^{\mathrm{\ell }}=v_4^{\mathrm{\ell }}{v}_7^{\mathrm{\ell }},{\tilde{e}}_6^{\mathrm{\ell }}=v_8^{\mathrm{\ell }}y,{\tilde{e}}_7^{\mathrm{\ell }}=v_3^{\mathrm{\ell }}{v}_9^{\mathrm{\ell }},$

with corresponding gaps
$g_1^{\mathrm{\ell }}=v_1^{\mathrm{\ell }}{v}_2^{\mathrm{\ell }},g_2^{\mathrm{\ell }}=v_3^{\mathrm{\ell }}{v}_4^{\mathrm{\ell }},g_3^{\mathrm{\ell }}=v_4^{\mathrm{\ell }}{v}_5^{\mathrm{\ell }},g_4^{\mathrm{\ell }}=v_5^{\mathrm{\ell }}{v}_1^{\mathrm{\ell }-1},g_5^{\mathrm{\ell }}=v_3^{\mathrm{\ell }-1}{v}_7^{\mathrm{\ell }},g_6^{\mathrm{\ell }}=v_8^{\mathrm{\ell }}x,g_7^{\mathrm{\ell }}=v_9^{\mathrm{\ell }-1}{v}_9^{\mathrm{\ell }}.$

We next show properties of the trees $T^{\mathrm{\ell }}$ and ${\tilde{T}}^{\mathrm{\ell }}$ resulting form the iterative construction.

For spanning trees on convex point sets we proved that finding shortest flip sequences is $\mathrm{𝖭𝖯}$-hard and we improved the current best lower bound on the diameter of the flip graph.

Interesting future directions include determining the exact diameters for flip graphs on point sets in convex as well as general position. We are also hopeful that our techniques for NP-hardness are fruitful in other settings. Very exciting is a recently announced breakthrough by Dorfer [20] concerning the complexity of computing the flip distance of triangulations on convex point sets, which is inspired by our methods.