Constrained Flips in Plane Spanning Trees

A flip between two plane spanning trees of $S$ is the operation that removes an edge from a tree and adds another edge such that the resulting structure is again a plane spanning tree. We also denote this operation as an unrestricted flip. A constrained version of flips are so-called compatible flips, for which the removed edge and the added edge are not allowed to cross. Rotations are a restricted subclass of compatible flips for which we additionally require the removed edge and the added edge to share a common vertex. The most restricted and local operation is a so called slide. A slide is an operation in which the added edge $(u,v)$ and the removed edge $(v,w)$ are again required to share a common vertex, additionally, the triangle $\mathrm{\Delta }(u,v,w)$ must not contain any other vertex and the edge $(u,w)$ has to be contained in the current tree. This can visually be interpreted as sliding the edge $(u,v)$ along the edge $(u,w)$ into the edge $(v,w)$. The (compatible) flip graph of plane spanning trees of $S$ has as its vertex set all such trees. Two vertices $T_1$, $T_2$ of this flip graph are connected with an edge if and only if $T_1$ can be transformed into $T_2$ by a single (compatible) flip. See Figure 1 for an example of flips in plane spanning trees.

Given an initial tree $T_{\text{in}}$ and a target tree $T_{\text{tar}}$, a (compatible) flip sequence from $T_{\text{in}}$ to $T_{\text{tar}}$ is a path from $T_{\text{in}}$ to $T_{\text{tar}}$ in the (compatible) flip graph. The (compatible) flip distance between $T_{\text{in}}$ and $T_{\text{tar}}$ is the length of a shortest path between $T_{\text{in}}$ and $T_{\text{tar}}$ in the flip graph. Any (compatible) flip sequence of this length is called a shortest (compatible) flip sequence. Similarly, we define the rotation graph, rotation sequences and the rotation distance. See Figure 2 for an illustration of the concepts.

For graph reconfiguration problems three natural questions arise: (1) Is the flip graph connected? (2) What is the diameter of the flip graph? (3) What is the complexity of computing shortest flip sequences between two specific configurations?

For any $n$-point set $S$, the flip graph of plane spanning trees on $S$ is known to be connected and has radius exactly $n-2$. The same holds for the compatible flip graph and the rotation graph; see [5, 6]. Hence, the diameter always lies between $n-2$ and $2n-4$. Since a lower bound for the diameter of $\lfloor \frac{3}{2}n\rfloor -5$ for convex $n$-point sets was shown in [12], the flip graph of plane spanning trees on convex point sets has received considerable attention. However, despite a prevailing conjecture that the diameter is at most $\frac{3}{2}n+O(1)$ [10, 14], even improving the upper bound to $2n-o(n)$ took surprisingly long. In the last few years, the upper bound for its diameter was improved to $2n-\mathrm{\Omega }(log(n))$ in [1] and soon after to $2n-\mathrm{\Omega }(\sqrt{n})$ in [10]. The upper bound from [10] is constructive and, though not stated explicitly, only uses compatible flips. Hence it also provides an upper bound for the diameter of the according compatible flip graph. In [8], the diameter was bounded from above by $cn$ with $c=\frac{1}{12}\left(22+\sqrt{2}\right)\approx 1.95$, which marked the first linear improvement over the initial bound from [5]. Very recently, a lower bound of $\frac{14}{9}n-O(1)$ and an upper bound of $\frac{5}{3}n-3$ on the diameter were achieved in [6], where the upper bound in general requires non-compatible flips. It is also known that any plane spanning tree can be transformed into any other using $\mathrm{\Theta }(n^2)$ many slides [4]. For a survey on further flip operations in trees with multiple flips in parallel as well as flips with labeled edges, we refer to [18].

For any graph reconfiguration problem, happy edges are edges that lie in both the initial and the target graph. A flip graph fulfills the happy edge property if there exists a shortest flip sequence between any two graphs that never flips happy edges. The happy edge property often is a good indication for the complexity of a graph reconfiguration problem. For example, for triangulations of simple polygons [3] and general point sets [16, 19], finding shortest flip sequences is computationally hard. The hardness proofs use counterexamples to the happy edge property as a key ingredient. Conversely, the happy edge property is known to hold for triangulations of convex polygons [20]. Though the complexity of finding shortest flip sequences is still open, the happy edge property yields multiple fixed-parameter tractable algorithms [7, 11, 15, 17]. Moreover, the happy edge property holds for plane perfect matchings of convex point sets and shortest flip sequences can be found in polynomial time [13]. For plane spanning trees in convex position the happy edge property was conjectured to hold [1, 14] for different types of flips. Up to now, it has only been disproved for slides [1].

We will start by improving upper bounds on the flip graph for restricted flip types in convex point sets. In Section 2 we improve the upper bound on the diameter of the compatible flip graph from $2n-\sqrt{n}$ in [10] to $\frac{5}{3}(n-1)$. Section 3 is dedicated to improving the upper bound on the rotation graph from $2n-O(1)$ in [5] to $\frac{7}{4}(n-1)$.

Afterwards we deal with the happy edge property. In Section 4 we provide a more refined framework for happy edge properties and in Section 5 we prove the happy edge property for compatible flips in convex point sets and provide a counterexample to the happy edge property for rotations.

Finally, in Section 6 we use variants of the happy edge property to show fixed-parameter tractability of the flip distance for both unrestricted and compatible flips.

Due to space restrictions, full technical details and proofs for statements marked with $(\star )$ are given in the arXiv Version of our paper [2].

We root the tree $T$ at $v$ and orient every edge away from $v$ such that $v$ forms the unique source of the oriented graph; see Figure 6 for an illustration. Now map each vertex in $S\setminus \{v\}$ to its incoming edge. $◀$

The pairing $\{({\rho }_{T_1,v}(w),{\rho }_{T_2,v}(w)\mid w\in S\setminus \{v\}\}$ induced by the bijection in Lemma 4 has all the desired properties. $◀$

For any two given plane spanning trees $T_{\text{in}}$ and $T_{\text{tar}}$, we apply the bijection from Corollary 5 with $v:=v_n$ to obtain a pairing of the edges of the two trees with all the mentioned properties. For an edge $e$ that is in bijection with a vertex $v_i$ we say that $e$ is attached to $v_i$. Note that each vertex $v_i$ with $i\in \{1,\mathrm{\dots },n-1\}$ has an attached edge from each of $T_{\text{in}}$ and $T_{\text{tar}}$, while $v_n$ has no attached vertices.

From this point on we consider the two trees presented in their linear representation, see Figure 3, such that $v_n$ is the rightmost vertex. The pairs of edges $(e_{\text{in}}=(v_i,v_j),e_{\text{tar}}=(v_i,v_k))$, where $v_i$ is the vertex where edges $e_{\text{in}}$ and $e_{\text{tar}}$ are attached to, can now be subdivided into multiple classes. We say that a pair of edges is …

• $\mathrm{■}$

  right-attached above if

• $\mathrm{■}$

  left-attached above if

• $\mathrm{■}$

  right-attached below if

• $\mathrm{■}$

  left-attached below

• $\mathrm{■}$

  diving if

• $\mathrm{■}$

  jumping if

We denote the respective sets of pairs in that order by $RA$, $LA$, $RB$ $LB$, $D$ and $J$. Additionally, we set $L=LA\cup LB$ and $R=RA\cup RB$. See Figure 7 for an illustration of the six types of edge pairs, as well as the two groups $L$ and $R$. We remark that happy edges that are left-attached fulfill both, the definition for left-attached above and the one left-attached below. This does not pose any problem, since in the parts of the proof where this is relevant, we will only consider the whole set $L$. By symmetry, the same can be said about right-attached happy edges. Another noteworthy observation is that we do not handle convex hull edges any differently than diagonals. There might even be happy convex hull edges that belong to different pairs. This will lead to cases in which we rotate happy (convex-hull) edges. We allow this on purpose, since we will see in Section 5 that the happy edge property does not hold for rotations.

The new upper bound on the diameter of the rotation graph is described by the following Theorem.

We will use Lemma 7 below to get the edges from three of the sets $L$, $R$, $J$, and $D$ “out of the way”. Then we will show that all edges from the remaining set can be perfectly flipped.

We pair the edges and vertices of $T$ via the bijection ${\rho }_{T,v_n}$. Further, for an arbitrary $j\in \{1,\mathrm{\dots },n-1\}$, we assign a gap to every vertex except $v_n$ by the following function (indices taken modulo $n$).

In other words, we choose one particular gap $(v_j,v_{j+1})$ that is not assigned to any vertex and the other gaps are assigned such that they contain their assigned vertex.

In the following lemma, $j$ is an arbitrary index, $I$ is a subset of the convex hull edges in $T$ that behave “nicely” with respect to ${\delta }_j$, and $K$ are all edges of $T$ that are incident to $v_n$. $I^{\ast }$ and $K^{\ast }$ are according subsets that are required to be present in the resulting tree $T^{\ast }$.

We refer to Figure 8 for an illustration of Lemma 7 applied to the tree from Figure 6.

We set $E_0={\rho }_{T,v_n}(\{v_k\mid k\in (I\cap I^{\ast })\cup (K\cap K^{\ast })\})$ and $T_0=T\setminus E_0$. Now consider the forest $T_{0,vis}$ of edges that are visible from $v_n$ in $T_0$. These are all edges for which no straight-line segment from $v_n$ to the edge is intersected by any other edge. Further, let $v_k$ be a vertex of degree one in $T_{0,vis}$. Then the only edge incident to $v_k$ in $T_{0,vis}$ is ${\rho }_{T,v_n}(v_k)$. In particular, if $k\in I^{\ast }$ then ${\delta }_j(v_k)$ does not contain any edge and is visible from $v_n$, and if $k\in K^{\ast }$ then the straight-line segment between $v_n$ and $v_k$ is uncrossed.

We can execute a flip that exchanges the edge ${\rho }_{T,v_n}(v_k)$ with the edge ${\delta }_j(v_k)$ (if $k\in I^{\ast }$) or $(v_n,v_k)$ if $k\in K^{\ast }$ to get a valid tree. We replace $E_0\leftarrow E_0\cup \{{\delta }_j(v_k)\}$ (resp. $E_0\leftarrow E_0\cup \{(v_n,v_k)\}$) and $T_0\leftarrow T_0\setminus \{{\delta }_j(v_k)\}$ (resp. $T_0\leftarrow T_0\setminus \{(v_n,v_k)\}$) and repeat the process. We repeat until $E_0=T$. This takes at most $n-1-|I\cap I^{\ast }|-|K\cap K^{\ast }|$ rotations, since the cardinality of $E_0$ increases by one in every iteration. $◀$

A gap $(v_i,v_{i+1})$ in a tree $T$ is called empty if the edge $(v_i,v_{i+1})$ is not part of $T$. Note that in the target tree $T^{\ast }$ from Lemma 7, the gap $(v_j,v_{j+1})$ is empty. Moreover, by setting $K^{\ast }=\mathrm{\varnothing }$, a flip sequence as in Lemma 7 can be used to rotate all edges to the convex hull such that all convex hull edges that point away from $v_n$ do not have to be rotated.

Let $T_{\text{in}}=T_0$, $T_1$,…,$T_k=T_{\text{tar}}$ be a compatible flip sequence that removes a happy edge $e$ in a flip from $T_i$ to $T_{i+1}$. By Lemma 20, there exists a shortest compatible flip sequence from $T_{i+1}=T_{i+1}^{\prime }$,$T_{i+2}^{\prime }$,…,$T_{\text{tar}}^{\prime }=T_{\text{tar}}$ that only uses parking edges from the convex hull boundary. Since $e$ crosses neither an edge of $T_{\text{in}}\cap T_{\text{tar}}$ nor one on the convex hull boundary, $e$ crosses no edge in the flip sequence $T_0$,…,$T_i$,$T_{i+1}^{\prime }$,…,$T_{\text{tar}}$. Hence, by Lemma 18, we can construct a shorter flip sequence that preserves $e$. $◀$

By Proposition 16(i) and the example in Figure 12, Theorem 21 is best possible in the sense that there are flip sequences that flip a happy edge and cannot be shortened by two flips.

When we restrict the flip even further by only allowing edge rotations instead of all compatible exchanges, the happy edge property no longer holds. Also for the more restricted edge slides, the happy edge property does not hold, see [4] for the general case, and [1] for convex point sets.

Figure 14 shows a counterexample to the happy edge property for convex point sets with rotations. Assume the happy edge property would hold. Then the happy edge that passes through the middle of our convex polygon would split the tree into two proper subtrees. In each such subtree, the unhappy edge has a fixed position where it has to go. Since the initial position and the target position of the unhappy edge do not share any vertex, we need at least two rotations to get each unhappy edge from one position to the other. This gives us a minimum length of four for any flip sequence that preserves happy edges.

The flip sequence in Figure 14 only uses three rotations. Therefore, the happy edge property does not hold for the reconfiguration of plane spanning trees with rotations.

For the unrestricted flip we define good happy edges. All happy edges on the convex hull are good happy edges. Further, a happy edge $e$ that does not lie on the convex hull splits the point set into two parts. If one of the two parts contains only happy edges, then $e$ is a good happy edge as well.

Now consider the tree $N(T_{\text{in}})$ that is obtained from $T_{\text{in}}$ from exhaustively contracting happy leaves and paths of happy edges along the convex hull as in Lemma 22. We consider the dual tree of $N(T_{\text{in}})$, whose vertices are the faces of $N(T_{\text{in}})\cup \{\text{convex hull edges}\}$ except the outer face and which contains edge between two vertices if and only if their corresponding faces share an edge of $N(T_{\text{in}})$.

Let there be a total of $t$ unhappy edges. Then there are a total of $t-1$ paths $P_1$,…,$P_{t-1}$ that fit the form of Claim 25. Let $l_1$,…,$l_{t-1}$ denote their number of happy edges in some order. Any flip sequence of length $k$ gets to spend a total of at most $k-t$ flips on all these happy edges combined. We enumerate all subsets of $\{P_1,\mathrm{\dots },P_{t-1}\}$ and if their number of happy edges sums up to less than $\frac{k-t}{2}$, then we consider an instance that contains all the faces that contain unhappy edges and the faces along the paths in the subset. Then the total remaining tree contains at most $k$ unhappy edges from $T_{\text{in}}$ and $k$ unhappy edges from $T_{\text{tar}}$. That gives a total of at most $2k$ unhappy edges and a total of at most $4k$ vertices. Additionally, we have a total of less than $0.5k$ edges from faces with only happy edges. This gives another $0.5k$ vertices. So we have at most $4.5k$ vertices in our reduced forest. Brute forcing the optimal solution gives us a total of $4.5k-1$ possible edges to remove and a total of at most $\left(\genfrac{}{}{0pt}{}{4.5k}{2}\right)$ positions to add edges for every flip. This gives us a total runtime of $O^{\ast }\left(2^k{\left(4.5k\left(\genfrac{}{}{0pt}{}{4.5k}{2}\right)\right)}^k\right)=O^{\ast }({(91.125k^3)}^k)$ based on the number of flip sequences that we have to check.

Figure 16 gives an intuitive idea, where the improvement comes from. We cut the point set along all happy diagonals such that the new instances have all their happy edges on the convex hull. $◀$

Next, we prove the existence of a faster FPT-algorithm for compatible flips that is based on the parking edge property.

We divide the point set into components by cutting along happy edges and then find the shortest flip sequence for every remaining component individually, see Figure 16. Observe that all the happy edges in these components are convex hull edges. If all edges in a component are happy, do not flip any edge in it. By Lemma 20 there exists a shortest flip sequence that only uses edges from $T_{\text{in}}$, $T_{\text{tar}}$ or the convex hull.

Now let $ϵ>0$ be fixed and $t=\lceil \frac{1}{ϵ}\rceil$. Let $C_1$,…,$C_m$ be all components with $\le t$ unhappy edges. Determine the respective flip distances $k_j$ from $T_{\text{in}}^{C_j}$ to $T_{\text{tar}}^{C_j}$ via brute force and discard all the instances. For checking whether the remaining instances have a combined flip distance of $k^{\prime }=k_c-k_1-\mathrm{\dots }-k_m$ one has to check ${((2+ϵ)k^{\prime 2})}^{k^{\prime }}$ different flip sequences. There are $k^{\prime }$ choices to remove an edge and every component with $l\ge n$ diagonals has $l+1\le l(1+\frac{1}{t})\le l(1+ϵ)$ holes in the convex hull where we can add edges. $◀$