Computing Distances on Graph Associahedra Is Fixed-Parameter Tractable
Abstract
An elimination tree of a connected graph is a rooted tree on the vertices of obtained by choosing a root and recursing on the connected components of to obtain the subtrees of . The graph associahedron of is a polytope whose vertices correspond to elimination trees of and whose edges correspond to tree rotations, a natural operation between elimination trees. These objects generalize associahedra, which correspond to the case where is a path. Ito et al. [ICALP 2023] recently proved that the problem of computing distances on graph associahedra is NP-hard. In this paper we prove that the problem, for a general graph , is fixed-parameter tractable parameterized by the distance . Prior to our work, only the case where is a path was known to be fixed-parameter tractable. To prove our result, we use a novel approach based on a marking scheme that restricts the search to a set of vertices whose size is bounded by a (large) function of .
Keywords and phrases:
graph associahedra, elimination tree, rotation distance, parameterized complexity, fixed-parameter tractable algorithm, combinatorial shortest path, reconfigurationCategory:
Track A: Algorithms, Complexity and GamesFunding:
Luís Felipe I. Cunha: FAPERJ-JCNE (E-26/201.372/2022) and CNPq-Universal (406173/ 2021-4).Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Fixed parameter tractability ; Mathematics of computing CombinatoricsRelated Version:
The full version of this article is permanently available here: http://arxiv.org/abs/2504.18338Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

1 Introduction
Given a connected and undirected graph , an elimination tree of is any rooted tree that can be defined recursively as follows. If , then consists of a single root vertex . Otherwise, a vertex is chosen as the root of , and an elimination tree is created for each connected component of . Each root of these elimination trees of is a child of in . For a disconnected graph , an elimination forest of is the disjoint union of elimination trees of the connected components of . Equivalently, an elimination forest of a graph is a rooted forest (that is, a forest with a root in every connected component) on vertex set such that for each edge , vertex is an ancestor of vertex in , or vice versa.
Figure 1 illustrates an example of two elimination trees and of a graph . With slight (and standard) abuse of notation, we use the same labels for the vertices of a graph and any of its elimination trees. Note that an elimination tree is unordered, i.e., there is no ordering associated with the children of a vertex in the tree. Similarly, there is no ordering among the elimination trees in an elimination forest.
Elimination trees have been studied extensively in various contexts, including graph theory, combinatorial optimization, polyhedral combinatorics, data structures, or VLSI design; see the recent paper by Cardinal, Merino, and Mütze [7] and the references therein. In particular, elimination trees play a prominent role in structural and algorithmic graph theory, as they appear naturally in several contexts. As a relevant example, the treedepth of a graph is defined as the minimum height of an elimination forest of [26].
Given a class of combinatorial objects and a “local change” operation between them, the corresponding flip graph has as vertices the combinatorial objects, and its edges connect pairs of objects that differ by the prescribed change operation. In this article, we focus on the case where this class of combinatorial objects is the set of elimination forests of a graph . For these objects, the commonly considered “local change” operation is that of edge rotation defined as follows, where we suppose for simplicity that is connected. Given an elimination tree of a graph , the rotation of an edge , with being the parent of , creates another elimination of , denoted by , obtained, informally, by just swapping the choice of and in the recursive definition of (that is, in the so-called elimination ordering), and updating the parent of the subtrees rooted at accordingly; see Figure 2 for an illustration. The formal definition can be found in Subsection 3.1 (cf. 2).
For example, in Figure 1, . The definition of the rotation operation clearly implies that it is self-inverse with respect to any edge, that is, for any elimination tree of a graph and any edge , it holds that . The rotation distance between two elimination trees of a graph , denoted by , is the minimum number of rotations it takes to transform into . The self-invertibility property of rotations discussed above implies that .
It is well known that for any graph , the flip graph of elimination forests of under tree rotations is the skeleton of a polytope, referred to as the graph associahedron and that was introduced by Carr, Devadoss, and Postnikov [16, 11, 29]. For the particular cases of being a complete graph, a cycle, a path, a star, or a disjoint union of edges, is the permutahedron, the cyclohedron, the (standard) associahedron, the stellohedron, or the hypercube, respectively; see the introduction of [7] for nice figures to illustrate these objects.
Graph associahedra naturally generalize associahedra, which correspond to the particular case where is a path. As mentioned in [7], the associahedron has a rich history and literature, connecting computer science, combinatorics, algebra, and topology [32, 22, 18, 30]. See the introduction of the paper by Ceballos, Santos, and Ziegler [12] for a historical account. In an associahedron, each vertex corresponds to a binary tree over a set of elements, and each edge corresponds to a rotation operation between two binary trees, an operation used in standard online binary search tree algorithms [1, 17, 33]. Binary trees are in bijection with many other Catalan objects such as triangulations of a convex polygon, well-formed parenthesis expressions, Dyck paths, etc. [34]. For instance, in triangulations of a convex polygon, the rotation operation maps to another simple operation, known as a flip, which removes the diagonal of a convex quadrilateral formed by two triangles and replaces it by the other diagonal.
Related work.
Distances on graph associahedra have been object of intensive study. Probably, the most studied parameter is the diameter, that is, the maximum distance between two vertices of . A number of influential articles either determine the diameter exactly, or provide lower and upper bounds, or asymptotic estimates, for the cases where the underlying graph is a path [32, 30], a star [25], a cycle [31], a tree [25, 6], a complete bipartite graph [8], a caterpillar [3], a trivially perfect graph [8], a graph in which some width parameter (such as treedepth or treewidth) is bounded [8], or a general graph [25].
Our focus is on the algorithmic problem of determining the distance between two vertices of , or equivalently, determining the rotation distance between two given elimination trees of a graph . There are very few cases where this problem is known to be solvable in polynomial time, namely when is a complete graph (folklore), a star [9], or a complete split graph [9]. The complexity of the case where is a path is a notorious long-standing open problem. On the positive side, for being a path, there exist a polynomial-time -approximation algorithm [15] and several fixed-parameter tractable (FPT) algorithms when the distance is the parameter [14, 20, 21, 23, 24]. It is worth mentioning that there are some hardness results on generalized settings [23, 27, 2] and polynomial-time algorithms for some type of restricted rotations [13].
Our result.
The NP-hardness result of Ito et al. [19] (see also [10]) paves the way for studying the parameterized complexity of the problem of computing distances on graph associahedra. Thus, in this article we are interested in the following parameterized problem, where we consider the natural parameter, that is, the desired distance.
As mentioned above, Rotation Distance was known to be polynomial-time solvable on complete graphs, stars, and complete split graphs [9], and FPT algorithms were only known on paths [14, 20, 21, 23, 24]. In this article we vastly generalize the known results by providing an FPT algorithm to solve the Rotation Distance problem for a general input graph . More precisely, we prove the following theorem.
Theorem 1.
The Rotation Distance problem can be solved in time , with
In particular, Theorem 1 yields a linear-time algorithm to solve Rotation Distance for every fixed value of the distance . To the best of our knowledge, this is the first positive algorithmic result for the general Rotation Distance problem (i.e., with no restriction on the input graph ), and we hope that it will find algorithmic applications in the many contexts where graph associahedra arise naturally [16, 11, 29, 7, 25, 19]. Our result can also been seen through the lens of the very active area of the parameterized complexity of graph reconfiguration problems; see [4] for a recent survey.
Organization.
In Section 2 we present an overview of the main ideas of the algorithm of Theorem 1, which may serve as a road map to read the rest of the article. In Subsection 3.1 we provide some preliminaries and fix our notation, in Section 3 we formally present our FPT algorithm (split into several subsections), and in Section 4 we discuss several directions for further research. Due to space limitations, the proofs of the statements marked with “” can be found in the full version available online.
2 Overview of the main ideas of the algorithm
Our approach to obtain an FPT algorithm to solve Rotation Distance is novel, and does not build on previous work. Given two elimination trees and of a connected graph and a positive integer , our goal is to decide whether there exists what we call an -rotation sequence from to , for some , that is, an ordered list of edges to be rotated in order to obtain from , going through the intermediate elimination trees (all of the same graph ); see Subsection 3.1 for the formal definition. At a high level, our approach is based on identifying a subset of marked vertices , of size bounded by a function of , so that we can assume that the desired rotation sequence uses only vertices in . Once this is proved, an FPT algorithm follows directly by applying brute force and guessing all possible rotations using vertices in .
A crucial observation (cf. 3) is that a rotation may change the set of children of at most three vertices (but the parent of arbitrarily many vertices, such as the roots of and in Figure 2). Motivated by this, we say that a vertex is -children-bad if its set of children in is different from its set of children in . By 3, we may assume (cf. 5) that we are dealing with an instance in which the number of -children-bad vertices is at most .
In a first step, we prove (cf. 7) that we can assume that the desired sequence of at most rotations to transform into uses only vertices lying in the union of the balls of radius around -children-bad vertices of , which we denote by . The proof of 7 exploits, in particular, the fact that a rotation may increase or decrease vertex distances (in the corresponding trees) by at most one (cf. Equation 1). This is then used to show that if a rotation uses some vertex outside of , then it can be “simplified” into another one that does not (cf. Figure 3).
By 7, we restrict henceforth to rotations using only vertices in . We can consider each connected component of , since it can be easily seen that we can assume that there are at most of them. By definition of , the diameter of such a component is (cf. Equation 3). Thus, the “only” obstacle to obtain the desired FPT algorithm is that the vertices in can have an arbitrarily large degree. Note that in the particular case where the underlying graph has bounded degree, the maximum degree of any elimination tree of is bounded, and therefore in that case is bounded by a function of , and an FPT algorithm follows immediately. To the best of our knowledge, this result was not known for graphs other than paths.
Our strategy to deal with high-degree vertices in is as follows. Fix one connected component of . Our goal is to identify a subset of size bounded by a function of , such that we can restrict our search to rotations using only vertices in . To find such a “small” set , we define the notion of type of a vertex , in such a way that the number of different types is bounded by a function of . Then, we will prove via our marking algorithm that it is enough to keep in , for each type, a number of vertices bounded again by a function of .
Before defining the types, we need to define the trace of a vertex in . To get some intuition, look at the rotation depicted in Figure 2. Note that, for each of the subtrees that are children of in , what determines whether they are children of or in the resulting subtree is whether some vertex in is adjacent to or not. Iterating this idea, if we are about to perform at most rotations starting from , then the behavior of such a subtree , assuming that no vertex of it is used by a rotation, is determined by its neighborhood in a set of ancestors of size at most the diameter of , and this is what the trace is intended to represent. That is, the trace of a vertex in , denoted by , captures “abstractly” the neighborhood of the whole subtree rooted at among (the ordered set of) its ancestors within the designated vertex set ; see 11 for the formal definition of trace and Figure 4 for an example. We stress that, when considering the neighborhood in the set of ancestors, we look at the whole subtree rooted at , and not only at its restriction to the set .
Equipped with the definition of trace, we can define the notion of type, which is somehow involved (cf. 12) and whose intuition behind is the following. For our marking algorithm to make sense, we want that if two vertices with the same parent (called -siblings) have the same type (within ), denoted by , and an -rotation sequence from to uses some vertex from but uses no vertex in , then there exists another -rotation sequence from to that uses vertices in instead of those in . To guarantee this replacement property, we need a stronger condition than just and having the same trace. Informally, we need them to have the same “variety of traces among their children within ”. More formally, this leads to a recursive definition where, in the leaves of (that are not necessarily leaves of ), the type corresponds to the trace, and for non-leaves, the type is defined by the trace and by the number of children of each possible lower type. Note that, a priori, the number of children of a given type may be unbounded, which would rule out the objective of bounding the number of types as a function of . To overcome this obstacle, the crucial and simple observation is that at most subtrees rooted at a vertex of contain vertices used by the desired rotation sequence (cf. 16). This implies that if there are at least -siblings of the same type, necessarily the whole subtree of at least one of them, say , will not be used by , implying that (and its whole subtree) achieves the desired parent in without being used by , and the same occurs to any other -sibling of the same type. Thus, keeping track of the existence of at least such children (regardless of their actual number) is enough to capture this “static” behavior, and allows us to shrink the possible distinct numbers to keep track of to a function of (cf. Equation 4, where the “” is justified by the previous discussion). Finally, for technical reasons we also incorporate into the type of a vertex its desired parent in , in case it defers from its parent in (cf. function ). See 12 for the formal definition of type and Figure 5 for an example with .
We prove (cf. 13) that the number of types is indeed bounded by a (large) function depending only on , and this function is what yields the upper bound on the asymptotic running time of the FPT algorithm of Theorem 1. Moreover, we show (cf. 14) that the type of a vertex can be computed in time . We then use the notion of type and the bound given by 13 to define the desired set of size bounded by a function of . In order to find , we apply a marking algorithm on , that first identifies a set of pre-marked vertices, whose size is not necessarily bounded by a function of , and then “prunes” this set in a root-to-leaf fashion to find the desired set of marked vertices of appropriate size. See Figure 6 for an example of the marking algorithm for . We define (where denotes the set of connected components), and we call it the set of marked vertices of . We prove (cf. 15) that the size of is roughly equal to the number of types, and that the set can be computed in time FPT.
Once we have our set of marked vertices at hand, it remains to prove that we can restrict the rotations to use only vertices in . This is proved in our main technical result (cf. 17), whose proof critically exploits the recursive definition of the types. In a nutshell, we consider an -rotation sequence from to , for some , minimizing, among all -rotation sequences from to , the number of used vertices in . Our goal is to define another -rotation sequence from to using strictly less vertices in than , contradicting the choice of . To this end, let be a lowest (with respect to the distance to ) non-marked vertex of that is used by . We distinguish two cases.
In Case 1, we assume that has a marked -sibling with (cf. Figure 8). It is not difficult to prove that we can define from by just replacing with in all the rotations of involving (cf. 18 and 19).
In Case 2, all -siblings of with , if any, are non-marked. In this case, in order to define another -rotation sequence from to that uses more marked vertices than , we need to modify in a more global way than in Case 1. Namely, in order to define , we need a more global (and involved) replacement, which we achieve via what we call a representative function . To define , we first guarantee the existence of a very helpful vertex that is a non-marked ancestor of having a marked -sibling of the same type such that no vertex in is used by ; see 20 and Figure 9. Exploiting the recursive definition of type, we then define our representative function , mapping vertices used by in to vertices in of the same type (cf. 21), and prove that we can define from by replacing each vertex used by in by its image via in in all the rotations of involving (cf. 22 and 23).
3 Formal description of the FPT algorithm
In this section we present our FPT algorithm to solve the Rotation Distance problem. We start in Subsection 3.1 by providing some preliminaries and useful observations about what we call good and bad vertices. In Subsection 3.2 we show that we can assume that all the rotations involve vertices within balls of small radius around bad vertices. In Subsection 3.3 we describe our marking algorithm, using the definition of type, and show that the set of marked vertices can be computed in FPT time. In Subsection 3.4 we prove our main technical result (17), stating that we can restrict the desired rotations to involve only marked vertices. In Subsection 4.5 of the full version we wrap up the previous results to prove Theorem 1. We stress that, as discussed in Section 2, once we have at hand the set of marked vertices of bounded size, the algorithm consists just in a naive brute-force search over all possible rotation using only vertices in , and this is why we omit the wrap up in this extended abstract.
3.1 Preliminaries and useful observations
We use standard notation about graphs and parameterized complexity, and we refer to the full version for additional preliminaries. Here we mostly focus on rooted trees and rotations.
For a positive integer , we let denote the set . If is a function between two sets and and , we denote by the restriction of to .
Rooted trees.
For a rooted tree , we use to denote its root. For a vertex , we denote by the unique parent of in (or the empty set if is the root), by the set of children of in , by the set of ancestors of in (including itself), and by the set of descendants of in (including itself). The strict ancestors (resp. descendants) of are the vertices in the set (resp. ). We denote by the subtree of rooted at . Two vertices are -siblings if .
Rotation of an edge in an elimination tree.
We provide the formal definition of the rotation operation, which has been already informally defined in the introduction (cf. Figure 2).
Definition 2 (rotation operation).
Let be an elimination tree of a graph and let with . The rotation of in creates another elimination tree of defined as follows, where for better readability we use :
-
1.
.
-
2.
.
-
3.
If , let . Then .
-
4.
.
-
5.
Let . If is adjacent in to some vertex in , then ; otherwise .
-
6.
For every vertex , .
A -rotation sequence from an elimination tree to another elimination tree (of the same graph ) is an ordered set of edges such that, letting inductively and, for , with , we have that . In other words, a -rotation sequence consists of the ordered list of the edges to be rotated in order to obtain from , going through the intermediate elimination trees (of the same graph ). Clearly, if and only if there exists an -rotation sequence from to for some . We say that a vertex is used by a rotation sequence if it is an endpoint of some of the edges that are rotated by .
Throughout the paper, we assume that all the considered elimination trees are of a same fixed input graph . For simplicity, we may assume henceforth that is connected.
Good and bad vertices.
Our algorithm exploits how a rotation in an elimination tree may affect the parents and the children of its vertices. Note that a single rotation of an edge , yielding an elimination tree , may change the parent of arbitrarily many vertices. Indeed, these vertices are the roots of the red subtrees in Figure 2, and the considered vertex may be adjacent to the root of arbitrarily many subtrees containing at least one vertex adjacent to : for each such root , but . As a concrete example, in Figure 1, but . On the other hand, item 6 of 2 implies that there are at most three vertices whose children set changes from to , namely as depicted in Figure 2. (Note that the sets of children of and always change, and that of changes provided that this vertex exists.) We state this observation formally, since it will be extensively used afterwards.
Observation 3.
One rotation may change the set of children of at most three vertices.
The above discussion motivates the following definition.
Definition 4 (bad vertices).
Given two elimination trees and , a vertex is -children-bad (resp. (T,T’)-parent-bad) if (resp. ). A vertex is -bad if it is -children-bad, or -parent-bad, or both. A vertex is -good if it is not -bad.
Note that contains no -children-bad (or -parent-bad, or just -bad) vertices if and only if , that is, if and only if . Also, note that a vertex is -children-bad, with , if and only if at least one of its children is -parent-bad. 3 directly implies the following necessary condition for the existence of a solution.
Observation 5.
Given two elimination trees and , if then the number of -children-bad vertices is at most .
5 is equivalent to saying that we can safely conclude that any instance of Rotation Distance with at least -children-bad vertices is a no-instance. Thus, we can assume henceforth that we are dealing with an instance of Rotation Distance containing at most -children-bad vertices.
3.2 Restricting the rotations to small balls around bad vertices
Our next goal is to prove (7) that we can assume that the desired sequence of at most rotations to transform into uses only edges whose both endvertices lie in the union of all the balls of appropriate radius (depending only on ) around -children-bad vertices of , whose number is bounded by a function of by 5.
In the next definition, for the sake of notational simplicity we omit , and from the notation , as we assume that they are already given, and fixed, as the input of our problem. We include in the considered set for technical reasons, namely in the proof of 9.
Definition 6 (union of balls of children-bad vertices).
Let be the set of -children-bad vertices. We define .
Lemma 7.
If , then there exists an -rotation sequence from to , with , using only vertices in .
Proof.
Let be an -rotation sequence from to , with . Let us denote by the number of edges in with at least one endvertex not in . Assuming that , we proceed to construct another -rotation sequence from to , with , such that . Repeating this procedure eventually yields a sequence as claimed in the statement of the lemma.
For , let be the -th edge of and let be the elimination tree obtained after the rotation of . Let also . For , we say that a vertex is affected by the rotation of if , and it is -affected if it is affected by the rotation of some edge in . Recall that a rotation affects at most three vertices, and that these vertices are within distance at most two in the original tree (cf. vertices in Figure 2). Moreover, any rotation may increase or decrease vertex distances by at most one, that is, for any and any two vertices , it holds that
(1) |
Let be the set of -affected vertices, and note that . The observation above about the fact that the (two or three) vertices affected by a rotation are within distance at most two (in the tree where the rotation is done), together with Equation 1, imply that for every , it holds that its diameter is linearly bounded by , namely
(2) |
Since by assumption , there exists such that or (or both); assume without loss of generality that . Let be the connected component of containing vertices and (note that they indeed lie in the same component of since edge belongs to ). Let be the set of -children-bad vertices, and recall that . See Figure 3.
Claim 8.
No vertex in is -children-bad.
Proof.
Suppose towards a contradiction that the statement does not hold, and let . Since (see Figure 3), the definition of implies that , contradicting Equation 2 because both and belong to .
Claim 9 ().
All vertices in are -good.
Relying on 9, we define from an -rotation sequence from to , with , as follows: consists of the (ordered) edges appearing in , except from those with both endvertices lying in the connected component of .
Claim 10 ().
is an -rotation sequence from to with and .
The above claim concludes the proof of the lemma.
By 7, we focus henceforth on trying to find an -rotation sequence from to , with , consisting only of edges with both endvertices in . First, we will consider each of the at most connected components of separately. In fact, we can get a better bound, as if has at least connected components, we can immediately conclude that we are dealing with a no-instance, since at least one rotation is needed in each component. Thus, we may assume that has at most connected components. On the other hand, since is defined as the union of at most balls of radius , it follows that every satisfies
(3) |
Thus, by Equation 3, the “only” obstacle to obtain the desired FPT algorithm is that the vertices in can have an arbitrarily large degree. Note that in the particular case where the underlying graph has bounded degree, for instance if is a path [14, 20, 21, 23], the maximum degree of any elimination tree of is bounded, and therefore in that case is bounded by a function of , and an FPT algorithm follows immediately. To the best of our knowledge, this result was not known for graphs other than paths (albeit, with a better running time than the one that results from just brute-forcing on the set , which is of the form ).
3.3 Description of the marking algorithm
Let henceforth be a connected component of , which we consider as a rooted tree with its own set of leaves, which are not necessarily leaves in . We define to be the vertex in closest to in . Before defining the types, we need to define the trace of a vertex in a designated vertex set .
Definition 11 (trace of a vertex in a component ).
Let be an elimination tree (of a graph ), let be a rooted subtree of corresponding to a connected component of , and let . The trace of in , denoted by , is a binary vector of dimension defined as follows (note that if , then its trace is empty). For , let be the ancestor of in such that . Then the -th coordinate of is if for some vertex , and otherwise.
See Figure 4 for an example of the trace of some vertices in a component .
For a vertex , let be equal to if , and to otherwise. Note that, by 5, the function can take up to distinct values when ranging over all .
Definition 12 (type of a vertex in a component ).
Let be an elimination tree (of a graph ), let be a rooted subtree of corresponding to a connected component of , and let . The type of vertex , denoted by , is recursively defined as follows, where is the set of types occurring in the children of :
-
If is a leaf of , then consists of the pair .
-
Otherwise, consists of a tuple , where is a mapping defined such that, for every ,
(4)
See Figure 5 for an example for of how the types are computed in a component .
Lemma 13.
The set has size bounded by a function , with
(5) |
Proof.
Let , and note that by Equation 3. For , let be the number of distinct types among the vertices in that are at distance exactly from in . Formally,
(6) |
By the definition of type, since, on the one hand, all vertices at distance from are leaves of , and the number of possible traces among leaves is at most , and on the other hand the term corresponds to the possible distinct values of the function . For every , Equation 4 implies that
(7) |
where the term again comes from the possible distinct values of the function , the term comes from the possible different traces within distance from , and the term follows from the fact that, for every , the function can take up to values for each type of a children of , together with the possibility that a type is not present among the children of . Note that a vertex with may have children being roots of any possible subtree with diameter at most , justifying the sum in Equation 7. Clearly, the upper bound of Equation 7 is maximized for , that is, for the children of , yielding the bound claimed in Equation 5.
Note that, in order to compute the type of a vertex in a component , the recursive definition of the types together with 13 easily imply the following observation, where the term comes from checking the neighborhood of within the set in the computation of the trace (cf. 11).
Observation 14.
Let be an elimination tree of a graph , let be a rooted subtree of corresponding to a connected component of , and let . Then can be computed in time , where is the function from 13.
We will now use the notion of type and the bound given by 13 to define the desired set of size bounded by a function of . In order to find , we apply a marking algorithm on , that first identifies a set of pre-marked vertices, whose size is not necessarily bounded by a function of , and then “prunes” this set in a root-to-leaf fashion to find the desired set of marked vertices of appropriate size.
Start with . For every vertex and every , do the following:
-
If , add the whole set to .
-
Otherwise, add to an arbitrarily chosen subset of of size .
Finally, add to . We define and we call it the set of pre-marked vertices of .
We are now ready to define our bounded-size set . Start with and for , proceed inductively as follows: if is a vertex with that already belongs to , add to the set . Finally, for every -children-bad vertex of that belongs to , we add to the set . This concludes the construction of . Note that if a vertex belongs to , then the whole set belongs to as well. We define , and we call it the set of marked vertices of . See Figure 6 for an example of the marking algorithm.
Lemma 15 ().
The set of marked vertices has size bounded by a function , where has the same asymptotic growth as the function given by 13. Moreover, can be computed in time .
3.4 Restricting the rotations to marked vertices
We now prove our main technical result (17), which immediately yields the desired FPT algorithm combined with 15 (whose proof uses 7), as discussed in Section 2. We first need an easy lemma that will be extensively used in the proof of 17; see Figure 7.
Lemma 16.
Let be an -rotation sequence from to , for some . For every vertex , there are at most vertices such that uses a vertex in each of the rooted subtrees .
Proof.
Assume towards a contradiction that there is a vertex having children, say , such that uses vertices with for . Then, since is made of at most rotations, by the pigeonhole principle necessarily there exist two children of and an integer such that , and none of occurs in any other rotation of other than . Since , it means that in the elimination tree where this rotation takes place, namely , it holds that . See Figure 7 for an illustration.
On the other hand, note that if is an elimination tree resulting from an elimination tree after the rotation of an edge , and are vertices of (and ) such that and , then necessarily , that is, necessarily the rotation involves at least one of and . See Figure 2 for a visualization of this claim, where the new edges that appear after the rotation of are and the edges between and some of the red subtrees: each of these new edges contains or .
Since because , and are -siblings, and , by the above paragraph there exists some integer , with , such that the rotation of contains at least one of and . This contradicts that fact that none of occurs in any other rotation of other than .
We are now ready to prove our main lemma.
Lemma 17.
If , then there exists an -rotation sequence from to , with , using only vertices in .
Proof.
Let be an -rotation sequence from to , for some , minimizing, among all -rotation sequences from to , the number of vertices in (that is, the non-marked vertices) used by . Note that exists by the hypothesis that . If there are no vertices in used by , then we are done, so assume that there are. Our goal is to define another -rotation sequence from to using strictly less vertices in than , contradicting the choice of and concluding the proof.
To this end, let be a furthest (with respect to the distance to ) non-marked vertex of that is used by . By 7, we can assume that . Let be the connected component of such that . For technical reasons, it will be helpful to assume that is not a leaf of . (This can be achieved, for instance, by observing that the analysis of the size of the components in 7 is not tight. Alternatively, we can just “artificially” increase their diameter by one –i.e., replacing with in the definition of – so that we can safely assume that the leaves of are never used by a rotation sequence.) Note that the choice of as a lowest (i.e., furthest) non-marked vertex of used by implies that for every vertex , the whole subtree remains intact throughout , meaning that it appears as a rooted subtree in all the intermediate elimination trees generated by the -rotation sequence . We distinguish two cases, the second one being considerably more involved, but that will benefit from the intuition developed in the first one.
Case 1: has a marked -sibling with .
Since is non-marked and by assumption it has some marked -sibling, the definition of (namely, that up to vertices of each type are recursively marked) and 16 imply that has some marked -sibling of the same type that is not used by . Let without loss of generality be such a -sibling of . Note that the choice of as a lowest non-marked vertex used by implies that the whole subtree remains intact throughout . See Figure 8 for an illustration.
In this case, we define from by just replacing with in all the rotations of involving . We need to prove that is well-defined (that is, that the edges to be rotated do exist in the intermediate elimination trees) and that it is an -rotation sequence from to . Once this is proved, this case is done, as uses strictly more marked vertices than .
Claim 18 ().
is a well-defined -rotation sequence.
Claim 19 ().
is an -rotation sequence from to .
Case 2: all -siblings of with , if any, are non-marked.
In this case, in order to define another -rotation sequence from to that uses more marked vertices than , we need to modify in a more global way than what we did in Case 1, where it was enough to replace vertex with a marked -sibling of the same type. To this end, the following claim guarantees the existence of a very helpful vertex . See Figure 9 for an illustration.
Claim 20.
There exists a unique vertex such that
-
is non-marked,
-
has a marked -sibling such that
-
–
, and
-
–
no vertex in is used by , and
-
–
-
is the vertex closest to satisfying the above properties.
Proof.
Since and , the definition of the marking algorithm implies that there exists a marked -sibling of with . Moreover, the fact that is defined by recursively marking up to vertices of each type implies, together with 16 and the fact that the desired vertex is non-marked, that there is some -sibling of with such that no vertex in is used by . Finally, we can clearly choose in a unique way as being the vertex closest to satisfying the above properties.
Note that Case 1 of the proof corresponds to the particular case where is equal to itself, but we prefer to separate both cases for the sake of readability. Intuitively, we will apply recursively the argument of Case 1 to the rooted subtrees and , starting with and , exploiting the definition of types to appropriately define the desired replacement of vertices to construct from .
Formally, let be the set of vertices in used by (so in Case 1, ), and let be the injective function defined as follows. For , let be the set of vertices in used by that are at distance exactly from vertex in . Note that some of the sets may be empty, and that contains . For every type occurring in a vertex in , let be the set of vertices of type in . Note that, if a set is non-empty, then defines a partition of into non-empty sets. Let be a set of marked vertices of type in of size (we shall prove in 21 that it exists). Then we define as any bijection between and . See Figure 9 for an illustration.
Claim 21 ().
The function is well-defined and injective.
For every vertex (recall that is the set of vertices in used by ), the vertex is called the representative of . Note that the function is also defined on , since it is used by . We now define from by replacing, in the rotations defining the sequence, every vertex by its representative .
Claim 22 ().
is a well-defined -rotation sequence.
Claim 23 ().
is an -rotation sequence from to .
By 23, is an -rotation sequence from to , and it uses strictly more marked vertices than , because no vertex of is marked (by the conditions in 20), and within there is at least one marked vertex, namely . This concludes Case 2.
In both cases, we have defined from another -rotation sequence from to using strictly less vertices in than , contradicting the choice of .
4 Further research
We proved that the Rotation Distance problem, for a general graph , can be solved in time , where is the function given by Theorem 1. This function is quite large, and it is worth trying to improve it. The growth of is mainly driven by the number of different types of vertices (cf. 12) that we consider in our marking algorithm. We need this recursive definition of type to guarantee that, when two vertices have the same type, then for each possible type and every integer at most the bound given in Equation 3, vertices and have the same number (up to ) of descendants of type within distance . This is exploited, for instance, in Case 2 of the proof of 17 to apply a recursive argument. It may possible to find a simpler argument in the replacement operation performed in the proof of 17 (using the representative function , and in that case, one may allow for a less refined notion of type, leading to a better bound.
Another natural direction is to investigate whether Rotation Distance admits a polynomial kernel parameterized by . So far, this is only known when the considered graph is a path, where even linear kernels are known[14, 24]; see Table 1. As an intermediate step, one may consider graphs of bounded degree, for which it seems plausible that 7 (restriction to few balls of bounded diameter) provides a helpful opening step.
Finally, Ito et al. [19] also proved the NP-hardness of a related problem called Combinatorial Shortest Path on Polymatroids, relying on the fact that graph associahedra can be realized as the base polytopes of some polymatroids [28]. To the best of our knowledge, the parameterized complexity of this problem has not been investigated.
References
- [1] Georgy M. Adel’son-Vel’skii and Evgenii M. Landis. An algorithm for the organization of information. Soviet Mathematics Doklady, 3:1259–1263, 1962. URL: https://zhjwpku.com/assets/pdf/AED2-10-avl-paper.pdf.
- [2] Oswin Aichholzer, Wolfgang Mulzer, and Alexander Pilz. Flip Distance Between Triangulations of a Simple Polygon is NP-Complete. Discrete & Computational Geometry, 54(2):368–389, 2015. doi:10.1007/S00454-015-9709-7.
- [3] Benjamin Aram Berendsohn. The diameter of caterpillar associahedra. In Proc. of the 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 227 of LIPIcs, pages 14:1–14:12, 2022. doi:10.4230/LIPICS.SWAT.2022.14.
- [4] Nicolas Bousquet, Amer E. Mouawad, Naomi Nishimura, and Sebastian Siebertz. A survey on the parameterized complexity of reconfiguration problems. Computer Science Review, 53:100663, 2024. doi:10.1016/J.COSREV.2024.100663.
- [5] Jean Cardinal, Linda Kleist, Boris Klemz, Anna Lubiw, Torsten Mütze, Alexander Neuhaus, and Lionel Pournin. Working grup 4.2: Rotation distance between elimination trees. Report from Dagstuhl Seminar 22062: Computation and Reconfiguration in Low-Dimensional Topological Spaces, page 35, 2022. URL: https://drops.dagstuhl.de/storage/04dagstuhl-reports/volume12/issue02/22062/DagRep.12.2.17/DagRep.12.2.17.pdf.
- [6] Jean Cardinal, Stefan Langerman, and Pablo Pérez-Lantero. On the diameter of tree associahedra. Electronic Journal of Combinatorics, 25(4):4, 2018. doi:10.37236/7762.
- [7] Jean Cardinal, Arturo Merino, and Torsten Mütze. Efficient generation of elimination trees and graph associahedra. In Proc. of the 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2128–2140, 2022. doi:10.1137/1.9781611977073.84.
- [8] Jean Cardinal, Lionel Pournin, and Mario Valencia-Pabon. Diameter estimates for graph associahedra. Annals of Combinatorics, 26:873–902, 2022. doi:10.1007/s00026-022-00598-z.
- [9] Jean Cardinal, Lionel Pournin, and Mario Valencia-Pabon. The rotation distance of brooms. European Journal of Combinatorics, 118:103877, 2024. doi:10.1016/J.EJC.2023.103877.
- [10] Jean Cardinal and Raphael Steiner. Shortest paths on polymatroids and hypergraphic polytopes. CoRR, abs/2311.00779, 2023. doi:10.48550/arXiv.2311.00779.
- [11] Michael Carr and Satyan L. Devadoss. Coxeter complexes and graph-associahedra. Topology and its Applications, 153(12):2155–2168, 2006. doi:10.1016/j.topol.2005.08.010.
- [12] Cesar Ceballos, Francisco Santos, and Günter M. Ziegler. Many non-equivalent realizations of the associahedron. Combinatorica, 35(5):513–551, 2015. doi:10.1007/s00493-014-2959-9.
- [13] Sean Cleary. Restricted rotation distance between -ary trees. Journal of Graph Algorithms and Applications, 27(1):19–33, 2023. doi:10.7155/JGAA.00611.
- [14] Sean Cleary and Katherine St. John. Rotation distance is fixed-parameter tractable. Information Processing Letters, 109(16):918–922, 2009. doi:10.1016/J.IPL.2009.04.023.
- [15] Sean Cleary and Katherine St. John. A linear-time approximation algorithm for rotation distance. Journal of Graph Algorithms and Applications, 14(2):385–390, 2010. doi:10.7155/JGAA.00212.
- [16] Satyan L. Devadoss. A realization of graph associahedra. Discrete Mathematics, 309(1):271–276, 2009. doi:10.1016/J.DISC.2007.12.092.
- [17] Leonidas J. Guibas and Robert Sedgewick. A dichromatic framework for balanced trees. In Proc. of the 19th Annual Symposium on Foundations of Computer Science (FOCS), pages 8–21, 1978. doi:10.1109/SFCS.1978.3.
- [18] Christophe Hohlweg and Carsten E. M. C. Lange. Realizations of the associahedron and cyclohedron. Discrete & Computational Geometry, 37(4):517–543, 2007. doi:10.1007/S00454-007-1319-6.
- [19] Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, and Yoshio Okamoto. Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra. In Prof. of the 50th International Colloquium on Automata, Languages, and Programming (ICALP), volume 261 of LIPIcs, pages 82:1–82:17, 2023. doi:10.4230/LIPIcs.ICALP.2023.82.
- [20] Iyad Kanj, Eric Sedgwick, and Ge Xia. Computing the flip distance between triangulations. Discrete & Computational Geometry, 58(2):313–344, 2017. doi:10.1007/S00454-017-9867-X.
- [21] Haohong Li and Ge Xia. An time FPT algorithm for convex flip distance. In Proc. of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 254 of LIPIcs, pages 44:1–44:14, 2023. doi:10.4230/LIPICS.STACS.2023.44.
- [22] Jean-Louis Loday. Realization of the Stasheff polytope. Archiv der Mathematik, 83:267–278, 2004. doi:10.1007/s00013-004-1026-y.
- [23] Anna Lubiw and Vinayak Pathak. Flip distance between two triangulations of a point set is NP-complete. Computational Geometry, 49:17–23, 2015. doi:10.1016/J.COMGEO.2014.11.001.
- [24] Joan M. Lucas. An improved kernel size for rotation distance in binary trees. Information Processing Letters, 110(12-13):481–484, 2010. doi:10.1016/J.IPL.2010.04.022.
- [25] Thibault Manneville and Vincent Pilaud. Graph properties of graph associahedra. CoRR, abs/1409.8114, 2010. arXiv:1409.8114.
- [26] Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. doi:10.1007/978-3-642-27875-4.
- [27] Alexander Pilz. Flip distance between triangulations of a planar point set is APX-hard. Computational Geometry, 47(5):589–604, 2014. doi:10.1016/J.COMGEO.2014.01.001.
- [28] Alex Postnikov, Victor Reiner, and Lauren Williams. Faces of generalized permutohedra. Documenta Mathematica, 13:207–273, 2008. doi:10.4171/DM/248.
- [29] Alexander Postnikov. Permutohedra, associahedra, and beyond. International Mathematics Research Notices, 2009(6):1026–1106, 2009. doi:10.1093/imrn/rnn153.
- [30] Lionel Pournin. The diameter of associahedra. Advances in Mathematics, 259:13–42, 2014. doi:10.1016/j.aim.2014.02.035.
- [31] Lionel Pournin. The asymptotic diameter of cyclohedra. Israel Journal of Mathematics, 219(2):609–635, 2017. doi:10.1007/s11856-017-1492-0.
- [32] Daniel D. Sleator, Robert E. Tarjan, and William P. Thurston. Rotation distance, triangulations, and hyperbolic geometry. Journal of the American Mathematical Society, 1(3):647–681, 1988. doi:10.1090/S0894-0347-1988-0928904-4.
- [33] Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32(3):652–686, 1985. doi:10.1145/3828.3835.
- [34] Richard P. Stanley. Catalan numbers. Cambridge University Press, 2015. doi:10.1017/CBO9781139871495.