Abstract 1 Introduction 2 Overview of the main ideas of the algorithm 3 Formal description of the FPT algorithm 4 Further research References

Computing Distances on Graph Associahedra Is Fixed-Parameter Tractable

Luís Felipe I. Cunha ORCID Instituto de Computação, Universidade Federal Fluminense, Brasil Ignasi Sau ORCID LIRMM, Université de Montpellier, CNRS, France Uéverton S. Souza ORCID Instituto de Computação, Universidade Federal Fluminense, Brasil
IMPA - Instituto de Matemática Pura e Aplicada, Rio de Janeiro, Brasil
Mario Valencia-Pabon ORCID Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
Abstract

An elimination tree of a connected graph G is a rooted tree on the vertices of G obtained by choosing a root v and recursing on the connected components of Gv to obtain the subtrees of v. The graph associahedron of G is a polytope whose vertices correspond to elimination trees of G and whose edges correspond to tree rotations, a natural operation between elimination trees. These objects generalize associahedra, which correspond to the case where G 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 G, is fixed-parameter tractable parameterized by the distance k. Prior to our work, only the case where G 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 k.

Keywords and phrases:
graph associahedra, elimination tree, rotation distance, parameterized complexity, fixed-parameter tractable algorithm, combinatorial shortest path, reconfiguration
Category:
Track A: Algorithms, Complexity and Games
Funding:
Luís Felipe I. Cunha: FAPERJ-JCNE (E-26/201.372/2022) and CNPq-Universal (406173/ 2021-4).
Ignasi Sau: French project ELiT (ANR-20-CE48-0008-01).
Uéverton S. Souza: CNPq (312344/2023-6), and FAPERJ (E-26/201.344/2021).
Mario Valencia-Pabon: French project Abysm (ANR-23-CE48-0017).
Copyright and License:
[Uncaptioned image] © Luís Felipe I. Cunha, Ignasi Sau, Uéverton S. Souza, and Mario Valencia-Pabon; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Fixed parameter tractability
; Mathematics of computing Combinatorics
Related Version:
The full version of this article is permanently available here: http://arxiv.org/abs/2504.18338
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

1 Introduction

Given a connected and undirected graph G, an elimination tree T of G is any rooted tree that can be defined recursively as follows. If V(G)={v}, then T consists of a single root vertex v. Otherwise, a vertex vV(G) is chosen as the root of T, and an elimination tree is created for each connected component of Gv. Each root of these elimination trees of Gv is a child of v in T. For a disconnected graph G, an elimination forest of G is the disjoint union of elimination trees of the connected components of G. Equivalently, an elimination forest of a graph G is a rooted forest F (that is, a forest with a root in every connected component) on vertex set V(G) such that for each edge uvE(G), vertex u is an ancestor of vertex v in F, or vice versa.

Figure 1 illustrates an example of two elimination trees T and T of a graph G. With slight (and standard) abuse of notation, we use the same labels for the vertices of a graph G 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.

Figure 1: A graph G and two of its elimination trees T and T, where the second one is obtained from the first one by the rotation of edge uv (in red).

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 G is defined as the minimum height of an elimination forest of G [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 G. For these objects, the commonly considered “local change” operation is that of edge rotation defined as follows, where we suppose for simplicity that G is connected. Given an elimination tree T of a graph G, the rotation of an edge uvE(T), with u being the parent of v, creates another elimination of G, denoted by 𝗋𝗈𝗍(T,uv), obtained, informally, by just swapping the choice of u and v in the recursive definition of T (that is, in the so-called elimination ordering), and updating the parent of the subtrees rooted at v accordingly; see Figure 2 for an illustration. The formal definition can be found in Subsection 3.1 (cf. 2).

Figure 2: On the left: An elimination tree T of a graph G with adjacent vertices u and v. Vertex v has four subtrees, and two of them, namely T2 and T3, contain vertices adjacent to vertex u in G. On the right: Elimination tree resulting from T by applying the rotation of uv. Since both G[V(T2){u}] and G[V(T3){u}] are connected, T2 and T3 become subtrees of u in 𝗋𝗈𝗍(T,uv).

For example, in Figure 1, T=𝗋𝗈𝗍(T,uv). The definition of the rotation operation clearly implies that it is self-inverse with respect to any edge, that is, for any elimination tree T of a graph G and any edge uvE(T), it holds that T=𝗋𝗈𝗍(𝗋𝗈𝗍(T,uv),vu). The rotation distance between two elimination trees T,T of a graph G, denoted by 𝖽𝗂𝗌𝗍(T,T), is the minimum number of rotations it takes to transform T into T. The self-invertibility property of rotations discussed above implies that 𝖽𝗂𝗌𝗍(T,T)=𝖽𝗂𝗌𝗍(T,T).

It is well known that for any graph G, the flip graph of elimination forests of G under tree rotations is the skeleton of a polytope, referred to as the graph associahedron 𝒜(G) and that was introduced by Carr, Devadoss, and Postnikov [16, 11, 29]. For the particular cases of G being a complete graph, a cycle, a path, a star, or a disjoint union of edges, 𝒜(G) 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 G 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 n 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 𝒜(G). 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 G 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 𝒜(G), or equivalently, determining the rotation distance between two given elimination trees of a graph G. There are very few cases where this problem is known to be solvable in polynomial time, namely when G is a complete graph (folklore), a star [9], or a complete split graph [9]. The complexity of the case where G is a path is a notorious long-standing open problem. On the positive side, for G being a path, there exist a polynomial-time 2-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].

Cardinal et al. [5] asked whether computing distances on general graph associahedra is NP-hard. Very recently, this question was answered positively by Ito et al. [19].

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 G. More precisely, we prove the following theorem.

Theorem 1.

The Rotation Distance problem can be solved in time f(k)|V(G)|, with

f(k)=kk22...2𝒪(k2),where the tower of exponentials has height at most (3k+1)4k=𝒪(k2).

In particular, Theorem 1 yields a linear-time algorithm to solve Rotation Distance for every fixed value of the distance k. 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 G), 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 T and T of a connected graph G and a positive integer k, our goal is to decide whether there exists what we call an -rotation sequence σ from T to T, for some k, that is, an ordered list of edges to be rotated in order to obtain T from T, going through the intermediate elimination trees T1,,T1 (all of the same graph G); see Subsection 3.1 for the formal definition. At a high level, our approach is based on identifying a subset of marked vertices MV(T), of size bounded by a function of k, so that we can assume that the desired rotation sequence σ uses only vertices in M. Once this is proved, an FPT algorithm follows directly by applying brute force and guessing all possible rotations using vertices in M.

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 T2 and T3 in Figure 2). Motivated by this, we say that a vertex vV(T) is (T,T)-children-bad if its set of children in T is different from its set of children in T. By 3, we may assume (cf. 5) that we are dealing with an instance in which the number of (T,T)-children-bad vertices is at most 3k.

In a first step, we prove (cf. 7) that we can assume that the desired sequence σ of at most k rotations to transform T into T uses only vertices lying in the union of the balls of radius 2k around (T,T)-children-bad vertices of T, which we denote by B𝖼𝖻. 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 B𝖼𝖻, 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 B𝖼𝖻. We can consider each connected component Z of T[B𝖼𝖻], since it can be easily seen that we can assume that there are at most k of them. By definition of B𝖼𝖻, the diameter of such a component Z is 𝒪(k2) (cf. Equation 3). Thus, the “only” obstacle to obtain the desired FPT algorithm is that the vertices in B𝖼𝖻 can have an arbitrarily large degree. Note that in the particular case where the underlying graph G has bounded degree, the maximum degree of any elimination tree of G is bounded, and therefore in that case |B𝖼𝖻| is bounded by a function of k, 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 B𝖼𝖻 is as follows. Fix one connected component Z of T[B𝖼𝖻]. Our goal is to identify a subset MZV(Z) of size bounded by a function of k, such that we can restrict our search to rotations using only vertices in MZ. To find such a “small” set MZV(Z), we define the notion of type of a vertex vV(Z), in such a way that the number of different types is bounded by a function of k. Then, we will prove via our marking algorithm that it is enough to keep in MZ, for each type, a number of vertices bounded again by a function of k.

Before defining the types, we need to define the trace of a vertex v in Z. To get some intuition, look at the rotation depicted in Figure 2. Note that, for each of the subtrees T1,,T4 that are children of v in T, what determines whether they are children of u or v in the resulting subtree is whether some vertex in Ti is adjacent to u or not. Iterating this idea, if we are about to perform at most k rotations starting from T, then the behavior of such a subtree Ti, 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 Z, and this is what the trace is intended to represent. That is, the trace of a vertex v in Z, denoted by 𝗍𝗋𝖺𝖼𝖾(T,Z,v), captures “abstractly” the neighborhood of the whole subtree rooted at v among (the ordered set of) its ancestors within the designated vertex set ZV(T); 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 T(v) rooted at v, and not only at its restriction to the set Z.

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 v,v with the same parent (called T-siblings) have the same type (within Z), denoted by τ(T,Z,v)=τ(T,Z,v), and an -rotation sequence σ from T to T uses some vertex from T(v) but uses no vertex in T(v), then there exists another -rotation sequence σ from T to T that uses vertices in T(v) instead of those in T(v). To guarantee this replacement property, we need a stronger condition than just v and v having the same trace. Informally, we need them to have the same “variety of traces among their children within Z”. More formally, this leads to a recursive definition where, in the leaves of Z (that are not necessarily leaves of T), 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 k. To overcome this obstacle, the crucial and simple observation is that at most k subtrees rooted at a vertex of T contain vertices used by the desired rotation sequence σ (cf. 16). This implies that if there are at least k+1 T-siblings of the same type, necessarily the whole subtree of at least one of them, say u, will not be used by σ, implying that u (and its whole subtree) achieves the desired parent in T without being used by σ, and the same occurs to any other T-sibling of the same type. Thus, keeping track of the existence of at least k+1 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 k (cf. Equation 4, where the “min” is justified by the previous discussion). Finally, for technical reasons we also incorporate into the type of a vertex its desired parent in T, in case it defers from its parent in T (cf. function 𝗐𝖺𝗇𝗍-𝗉𝖺𝗋𝖾𝗇𝗍(T,T,)). See 12 for the formal definition of type and Figure 5 for an example with k=2.

We prove (cf. 13) that the number of types is indeed bounded by a (large) function g(k) depending only on k, 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 g(k)|V(G)|. We then use the notion of type and the bound given by 13 to define the desired set MZZ of size bounded by a function of k. In order to find MZ, we apply a marking algorithm on Z, that first identifies a set MZ𝗉𝗋𝖾V(Z) of pre-marked vertices, whose size is not necessarily bounded by a function of k, and then “prunes” this set MZ𝗉𝗋𝖾 in a root-to-leaf fashion to find the desired set of marked vertices MZMZ𝗉𝗋𝖾 of appropriate size. See Figure 6 for an example of the marking algorithm for k=1. We define M=Z𝖼𝖼(T[B𝖼𝖻])MZ (where 𝖼𝖼 denotes the set of connected components), and we call it the set of marked vertices of T. We prove (cf. 15) that the size of M is roughly equal to the number of types, and that the set M can be computed in time FPT.

Once we have our set of marked vertices M at hand, it remains to prove that we can restrict the rotations to use only vertices in M. 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 T to T, for some k, minimizing, among all -rotation sequences from T to T, the number of used vertices in V(T)M. Our goal is to define another -rotation sequence σ from T to T using strictly less vertices in V(T)M than σ, contradicting the choice of σ. To this end, let vV(T)M be a lowest (with respect to the distance to 𝗋𝗈𝗈𝗍(T)) non-marked vertex of T that is used by σ. We distinguish two cases.

In Case 1, we assume that v has a marked T-sibling v with τ(T,Z,v)=τ(T,Z,v) (cf. Figure 8). It is not difficult to prove that we can define σ from σ by just replacing v with v in all the rotations of σ involving v (cf. 18 and 19).

In Case 2, all T-siblings v of v with τ(T,Z,v)=τ(T,Z,v), if any, are non-marked. In this case, in order to define another -rotation sequence σ from T to T 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 v that is a non-marked ancestor of v having a marked T-sibling v of the same type such that no vertex in T(v) 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 T(v) to vertices in T(v) of the same type (cf. 21), and prove that we can define σ from σ by replacing each vertex v used by σ in T(v) by its image via ρ in T(v) in all the rotations of σ involving v (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 M of bounded size, the algorithm consists just in a naive brute-force search over all possible rotation using only vertices in M, 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 p, we let [p] denote the set {1,2,,p}. If f:AB is a function between two sets A and B and AA, we denote by f|A the restriction of f to A.

Rooted trees.

For a rooted tree T, we use 𝗋𝗈𝗈𝗍(T) to denote its root. For a vertex vV(T), we denote by 𝗉𝖺𝗋𝖾𝗇𝗍(T,v) the unique parent of v in T (or the empty set if v is the root), by 𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,v) the set of children of v in T, by 𝖺𝗇𝖼𝖾𝗌𝗍𝗈𝗋𝗌(T,v) the set of ancestors of v in T (including v itself), and by 𝖽𝖾𝗌𝖼(T,v) the set of descendants of v in T (including v itself). The strict ancestors (resp. descendants) of v are the vertices in the set 𝖺𝗇𝖼𝖾𝗌𝗍𝗈𝗋𝗌(T,v){v} (resp. 𝖽𝖾𝗌𝖼(T,v){v}). We denote by T(v) the subtree of T rooted at v. Two vertices v,vV(T) are T-siblings if 𝗉𝖺𝗋𝖾𝗇𝗍(T,v)=𝗉𝖺𝗋𝖾𝗇𝗍(T,v).

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 T be an elimination tree of a graph G and let uvE(T) with 𝗉𝖺𝗋𝖾𝗇𝗍(T,v)=u. The rotation of uv in T creates another elimination tree 𝗋𝗈𝗍(T,uv) of G defined as follows, where for better readability we use T=𝗋𝗈𝗍(T,uv):

  1. 1.

    𝗉𝖺𝗋𝖾𝗇𝗍(T,u)=v.

  2. 2.

    u𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,v).

  3. 3.

    If u𝗋𝗈𝗈𝗍(T), let z=𝗉𝖺𝗋𝖾𝗇𝗍(T,u). Then 𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,z)=(𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,z){u}){v}.

  4. 4.

    𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,u)𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,u).

  5. 5.

    Let w𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,v). If u is adjacent in G to some vertex in T(w), then w𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,u); otherwise w𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,v).

  6. 6.

    For every vertex sV(G){u,v,z}, 𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,s)=𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,s).

A k-rotation sequence from an elimination tree T to another elimination tree T (of the same graph G) is an ordered set (e1,,ek) of edges such that, letting inductively T0:=T and, for i[k], Ti:=𝗋𝗈𝗍(Ti1,ei) with eiE(Ti1), we have that Tk=T. In other words, a k-rotation sequence consists of the ordered list of the k edges to be rotated in order to obtain T from T, going through the intermediate elimination trees T1,,Tk1 (of the same graph G). Clearly, 𝖽𝗂𝗌𝗍(T,T)k if and only if there exists an -rotation sequence from T to T for some k. We say that a vertex vV(T) 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 G. For simplicity, we may assume henceforth that G is connected.

Good and bad vertices.

Our algorithm exploits how a rotation in an elimination tree T may affect the parents and the children of its vertices. Note that a single rotation of an edge uvE(T), yielding an elimination tree T, 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 v may be adjacent to the root of arbitrarily many subtrees containing at least one vertex adjacent to u: for each such root r, 𝗉𝖺𝗋𝖾𝗇𝗍(T,r)=v but 𝗉𝖺𝗋𝖾𝗇𝗍(T,r)=u. As a concrete example, in Figure 1, 𝗉𝖺𝗋𝖾𝗇𝗍(T,s)=v but 𝗉𝖺𝗋𝖾𝗇𝗍(T,s)=u. On the other hand, item 6 of 2 implies that there are at most three vertices whose children set changes from T to T, namely u,v,z as depicted in Figure 2. (Note that the sets of children of u and v always change, and that of z 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 T and T, a vertex vV(T) is (T,T)-children-bad (resp. (T,T’)-parent-bad) if 𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,v)𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,v) (resp. 𝗉𝖺𝗋𝖾𝗇𝗍(T,v)𝗉𝖺𝗋𝖾𝗇𝗍(T,v)). A vertex vV(T) is (T,T)-bad if it is (T,T)-children-bad, or (T,T)-parent-bad, or both. A vertex vV(T) is (T,T)-good if it is not (T,T)-bad.

Note that T contains no (T,T)-children-bad (or (T,T)-parent-bad, or just (T,T)-bad) vertices if and only if T=T, that is, if and only if 𝖽𝗂𝗌𝗍(T,T)=0. Also, note that a vertex vV(T) is (T,T)-children-bad, with 𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,v), if and only if at least one of its children is (T,T)-parent-bad. 3 directly implies the following necessary condition for the existence of a solution.

Observation 5.

Given two elimination trees T and T, if 𝖽𝗂𝗌𝗍(T,T)k then the number of (T,T)-children-bad vertices is at most 3k.

5 is equivalent to saying that we can safely conclude that any instance (G,T,T,k) of Rotation Distance with at least 3k+1 (T,T)-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 3k (T,T)-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 k rotations to transform T into T uses only edges whose both endvertices lie in the union of all the balls of appropriate radius (depending only on k) around (T,T)-children-bad vertices of T, whose number is bounded by a function of k by 5.

In the next definition, for the sake of notational simplicity we omit T,T, and k from the notation B𝖼𝖻, as we assume that they are already given, and fixed, as the input of our problem. We include 𝗋𝗈𝗈𝗍(T) in the considered set for technical reasons, namely in the proof of 9.

Definition 6 (union of balls of children-bad vertices).

Let CV(T) be the set of (T,T)-children-bad vertices. We define B𝖼𝖻=NT2k[C𝗋𝗈𝗈𝗍(T)].

Lemma 7.

If 𝖽𝗂𝗌𝗍(T,T)k, then there exists an -rotation sequence from T to T, with k, using only vertices in B𝖼𝖻.

Proof.

Let σ be an -rotation sequence from T to T, with k. Let us denote by 𝗈𝗎𝗍(σ) the number of edges in σ with at least one endvertex not in B𝖼𝖻. Assuming that 𝗈𝗎𝗍(σ)1, we proceed to construct another -rotation sequence σ from T to T, with , such that 𝗈𝗎𝗍(σ)<𝗈𝗎𝗍(σ). Repeating this procedure eventually yields a sequence as claimed in the statement of the lemma.

For i[], let uivi be the i-th edge of σ and let Ti be the elimination tree obtained after the rotation of uivi. Let also T0=T. For i[], we say that a vertex wV(T) is affected by the rotation of uivi if 𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(Ti1,w)𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(Ti,w), 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 u,v,z in Figure 2). Moreover, any rotation may increase or decrease vertex distances by at most one, that is, for any i[] and any two vertices x,yV(T), it holds that

|𝖽𝗂𝗌𝗍Ti1(x,y)𝖽𝗂𝗌𝗍Ti(x,y)|1. (1)

Let AV(T) be the set of σ-affected vertices, and note that |A|3k. 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 Z𝖼𝖼(T[A]), it holds that its diameter is linearly bounded by k, namely

𝖽𝗂𝖺𝗆(Z)2k. (2)

Since by assumption 𝗈𝗎𝗍(σ)1, there exists j[] such that ujB𝖼𝖻 or vjB𝖼𝖻 (or both); assume without loss of generality that ujB𝖼𝖻. Let Z𝖼𝖼(T[A]) be the connected component of T[A] containing vertices uj and vj (note that they indeed lie in the same component of T[A] since edge ujvj belongs to σ). Let CV(T) be the set of (T,T)-children-bad vertices, and recall that B𝖼𝖻=NT2k[C𝗋𝗈𝗈𝗍(T)]. See Figure 3.

Figure 3: Illustration of the proof of 7. (T,T)-children-bad vertices are depicted in red, and the balls of radius 2k around them are shown with orange bubbles. The connected component Z𝖼𝖼(T[A]) containing both vertices uj and vj is depicted with thick blue edges. Distances in the figure are not meant to be accurate, and an extremity of an edge without a vertex means that T continues in that direction.
Claim 8.

No vertex in Z is (T,T)-children-bad.

Proof.

Suppose towards a contradiction that the statement does not hold, and let xZC. Since ujB𝖼𝖻 (see Figure 3), the definition of B𝖼𝖻 implies that 𝖽𝗂𝗌𝗍T(x,uj)2k+1, contradicting Equation 2 because both x and uj belong to Z.

Claim 9 ().

All vertices in Z are (T,T)-good.

Relying on 9, we define from σ an -rotation sequence σ from T to T, with , as follows: σ consists of the (ordered) edges appearing in σ, except from those with both endvertices lying in the connected component Z of T[A].

Claim 10 ().

σ is an -rotation sequence from T to T with and 𝗈𝗎𝗍(σ)<𝗈𝗎𝗍(σ).

The above claim concludes the proof of the lemma.

By 7, we focus henceforth on trying to find an -rotation sequence from T to T, with k, consisting only of edges with both endvertices in B𝖼𝖻. First, we will consider each of the at most 3k+1 connected components of T[B𝖼𝖻] separately. In fact, we can get a better bound, as if T[B𝖼𝖻] has at least k+1 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 T[B𝖼𝖻] has at most k connected components. On the other hand, since T[B𝖼𝖻] is defined as the union of at most 3k+1 balls of radius 2k, it follows that every Z𝖼𝖼(T[B𝖼𝖻]) satisfies

𝖽𝗂𝖺𝗆(Z)(3k+1)4k. (3)

Thus, by Equation 3, the “only” obstacle to obtain the desired FPT algorithm is that the vertices in B𝖼𝖻 can have an arbitrarily large degree. Note that in the particular case where the underlying graph G has bounded degree, for instance if G is a path [14, 20, 21, 23], the maximum degree of any elimination tree of G is bounded, and therefore in that case |B𝖼𝖻| is bounded by a function of k, 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 B𝖼𝖻, which is of the form 22𝒪(k)|V(G)|).

3.3 Description of the marking algorithm

Let henceforth Z be a connected component of T[B𝖼𝖻], which we consider as a rooted tree with its own set of leaves, which are not necessarily leaves in T. We define 𝗋𝗈𝗈𝗍(Z) to be the vertex in V(Z) closest to 𝗋𝗈𝗈𝗍(T) in T. Before defining the types, we need to define the trace of a vertex v in a designated vertex set ZV(T).

Definition 11 (trace of a vertex in a component Z).

Let T be an elimination tree (of a graph G), let Z be a rooted subtree of T corresponding to a connected component of B𝖼𝖻, and let vV(Z). The trace of v in Z, denoted by 𝗍𝗋𝖺𝖼𝖾(T,Z,v), is a binary vector of dimension 𝖽𝗂𝗌𝗍T(v,𝗋𝗈𝗈𝗍(Z)) defined as follows (note that if v=𝗋𝗈𝗈𝗍(Z), then its trace is empty). For i[𝖽𝗂𝗌𝗍T(v,𝗋𝗈𝗈𝗍(Z))], let ui𝖺𝗇𝖼𝖾𝗌𝗍𝗈𝗋𝗌(T,v) be the ancestor of v in T such that 𝖽𝗂𝗌𝗍T(v,ui)=i. Then the i-th coordinate of 𝗍𝗋𝖺𝖼𝖾(T,Z,v) is 1 if wuiE(G) for some vertex wV(T(v)), and 0 otherwise.

See Figure 4 for an example of the trace of some vertices in a component Z.

Figure 4: A component Z of T[B𝖼𝖻] and the trace of some of its vertices v1,,v7. Red dotted edges represent adjacencies in G. Note the 𝗍𝗋𝖺𝖼𝖾(T,Z,v3)=𝗍𝗋𝖺𝖼𝖾(T,Z,v6), even if v3 and v6 are not siblings in Z.

For a vertex vV(T), let 𝗐𝖺𝗇𝗍-𝗉𝖺𝗋𝖾𝗇𝗍(T,T,v) be equal to if 𝗉𝖺𝗋𝖾𝗇𝗍(T,v)=𝗉𝖺𝗋𝖾𝗇𝗍(T,v), and to 𝗉𝖺𝗋𝖾𝗇𝗍(T,v) otherwise. Note that, by 5, the function 𝗐𝖺𝗇𝗍-𝗉𝖺𝗋𝖾𝗇𝗍(T,T,v) can take up to 3k+1 distinct values when ranging over all vV(T).

Definition 12 (type of a vertex in a component Z).

Let T be an elimination tree (of a graph G), let Z be a rooted subtree of T corresponding to a connected component of B𝖼𝖻, and let vV(Z). The type of vertex v, denoted by τ(T,Z,v), is recursively defined as follows, where 𝗍𝗒𝗉𝖾-𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,Z,v):={τ(T,Z,u)u𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(Z,v)} is the set of types occurring in the children of v:

  • If v is a leaf of Z, then τ(T,Z,v) consists of the pair (𝗐𝖺𝗇𝗍-𝗉𝖺𝗋𝖾𝗇𝗍(T,T,v),𝗍𝗋𝖺𝖼𝖾(T,Z,v)).

  • Otherwise, τ(T,Z,v) consists of a tuple (𝗐𝖺𝗇𝗍-𝗉𝖺𝗋𝖾𝗇𝗍(T,T,v),𝗍𝗋𝖺𝖼𝖾(T,Z,v),fv), where fv:𝗍𝗒𝗉𝖾-𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,Z,v)[k+1] is a mapping defined such that, for every τ𝗍𝗒𝗉𝖾-𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,Z,v),

    fv(τ)=min{k+1,|{u𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(Z,v)τ(T,Z,u)=τ}|}. (4)

See Figure 5 for an example for k=2 of how the types are computed in a component Z.

Figure 5: A component Z of T[B𝖼𝖻] and the types of its vertices, for an instance with k=2. For the sake of simplicity, different types are depicted with different numbers. Assume that the leaves have only two possible types, namely 1 and 2, and that all non-leaf vertices at the same distance from the root have the same trace and the same function 𝗐𝖺𝗇𝗍-𝗉𝖺𝗋𝖾𝗇𝗍(T,T,). Note that the red vertices have the same type (namely, 4) because they both have one child of type 1 and at least k+1=3 children of type 2. Note also that the blue vertices have the same type (namely, 6) because they both have one child of type 3 and one child of type 4.
Lemma 13.

The set {τ(T,Z,v)vV(Z)} has size bounded by a function g(k), with

g(k)=k22...2𝒪(k2), where the tower of exponentials has height 𝖽𝗂𝖺𝗆(Z)=𝒪(k2). (5)

Proof.

Let d=𝖽𝗂𝖺𝗆(Z), and note that d(3k+1)4k=𝒪(k2) by Equation 3. For i[d], let τi be the number of distinct types among the vertices in V(Z) that are at distance exactly i from 𝗋𝗈𝗈𝗍(Z) in T. Formally,

τi=|{τ(T,Z,v)𝖽𝗂𝗌𝗍T(v,𝗋𝗈𝗈𝗍(Z))=i}|. (6)

By the definition of type, τd2d(3k+1) since, on the one hand, all vertices at distance d from 𝗋𝗈𝗈𝗍(Z) are leaves of Z, and the number of possible traces among leaves is at most 2d, and on the other hand the term 3k+1 corresponds to the possible distinct values of the function 𝗐𝖺𝗇𝗍-𝗉𝖺𝗋𝖾𝗇𝗍(T,T,v). For every i[d1], Equation 4 implies that

τi(3k+1)2ij=i+1d(k+2)τj, (7)

where the term 3k+1 again comes from the possible distinct values of the function 𝗐𝖺𝗇𝗍-𝗉𝖺𝗋𝖾𝗇𝗍(T,T,v), the term 2i comes from the possible different traces within distance i from 𝗋𝗈𝗈𝗍(Z), and the term k+2 follows from the fact that, for every vV(Z), the function fv can take up to k+1 values for each type τ of a children of v, together with the possibility that a type is not present among the children of v. Note that a vertex vV(T) with 𝖽𝗂𝗌𝗍(v,𝗋𝗈𝗈𝗍(Z))=i may have children being roots of any possible subtree with diameter at most di, justifying the sum in Equation 7. Clearly, the upper bound of Equation 7 is maximized for i=1, that is, for the children of 𝗋𝗈𝗈𝗍(Z), yielding the bound claimed in Equation 5.

Note that, in order to compute the type of a vertex in a component Z, the recursive definition of the types together with 13 easily imply the following observation, where the term |V(G)| comes from checking the neighborhood of T(v) within the set 𝖺𝗇𝖼𝖾𝗌𝗍𝗈𝗋𝗌(T,v) in the computation of the trace (cf. 11).

Observation 14.

Let T be an elimination tree of a graph G, let Z be a rooted subtree of T corresponding to a connected component of B𝖼𝖻, and let vV(Z). Then τ(T,Z,v) can be computed in time g(k)|V(G)|, where g(k) is the function from 13.

We will now use the notion of type and the bound given by 13 to define the desired set MZZ of size bounded by a function of k. In order to find MZ, we apply a marking algorithm on Z, that first identifies a set MZ𝗉𝗋𝖾V(Z) of pre-marked vertices, whose size is not necessarily bounded by a function of k, and then “prunes” this set MZ𝗉𝗋𝖾 in a root-to-leaf fashion to find the desired set of marked vertices MZMZ𝗉𝗋𝖾 of appropriate size.

Start with MZ𝗉𝗋𝖾=. For every vertex vV(Z) and every τ𝗍𝗒𝗉𝖾-𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(Z,v), do the following:

  • If |{u𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(Z,v)τ(Z,u)=τ}|k+1, add the whole set {u𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(Z,v)τ(Z,u)=τ} to MZ𝗉𝗋𝖾.

  • Otherwise, add to MZ𝗉𝗋𝖾 an arbitrarily chosen subset of {u𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(Z,v)τ(Z,u)=τ} of size k+1.

Finally, add 𝗋𝗈𝗈𝗍(Z) to MZ𝗉𝗋𝖾. We define M𝗉𝗋𝖾=Z𝖼𝖼(T[B𝖼𝖻])MZ𝗉𝗋𝖾 and we call it the set of pre-marked vertices of T.

We are now ready to define our bounded-size set MZMZ𝗉𝗋𝖾. Start with MZ={𝗋𝗈𝗈𝗍(Z)} and for i=0,,𝖽𝗂𝖺𝗆(Z)1, proceed inductively as follows: if vV(Z) is a vertex with 𝖽𝗂𝗌𝗍Z(v,𝗋𝗈𝗈𝗍(Z))=i that already belongs to MZ, add to MZ the set 𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(Z,v)MZ𝗉𝗋𝖾. Finally, for every (T,T)-children-bad vertex v of T that belongs to Z, we add to MZ the set 𝖺𝗇𝖼𝖾𝗌𝗍𝗈𝗋𝗌(Z,v). This concludes the construction of MZ. Note that if a vertex vV(Z) belongs to MZ, then the whole set 𝖺𝗇𝖼𝖾𝗌𝗍𝗈𝗋𝗌(Z,v) belongs to MZ as well. We define M=Z𝖼𝖼(T[B𝖼𝖻])MZ, and we call it the set of marked vertices of T. See Figure 6 for an example of the marking algorithm.

Figure 6: Example of the marking algorithm applied to a component Z of T[B𝖼𝖻], for an instance with k=1. As in Figure 5, different types are depicted with different numbers. Vertices inside blue squares belong to MZ𝗉𝗋𝖾, and red vertices belong to MZ.
Lemma 15 ().

The set MV(T) of marked vertices has size bounded by a function h(k), where h(k) has the same asymptotic growth as the function g(k) given by 13. Moreover, M can be computed in time h(k)|V(G)|.

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 T to T, for some k. For every vertex vV(T), there are at most k vertices u1,,uk𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,v) such that σ uses a vertex in each of the rooted subtrees T(u1),,T(uk).

Proof.

Assume towards a contradiction that there is a vertex vV(T) having k+1 children, say u1,uk+1, such that σ uses k+1 vertices u1,,uk+1 with urT(ur) for r[k+1]. Then, since σ=(e1,,e) is made of at most k rotations, by the pigeonhole principle necessarily there exist two children ui,uj of v and an integer p[] such that ep=uiuj, and none of ui,uj occurs in any other rotation of σ other than ep. Since ep=uiuj, it means that in the elimination tree where this rotation takes place, namely Tp1, it holds that uiujE(Tp1). See Figure 7 for an illustration.

On the other hand, note that if T2 is an elimination tree resulting from an elimination tree T1 after the rotation of an edge wzE(T1), and a,b are vertices of T1 (and T2) such that abE(T1) and abE(T2), then necessarily {a,b}{w,z}, that is, necessarily the rotation involves at least one of a and b. See Figure 2 for a visualization of this claim, where the new edges that appear after the rotation of uv are zv and the edges between u and some of the red subtrees: each of these new edges contains u or v.

Since uiujE(T0)=E(T) because uiT(ui),ujT(uj), and ui,uj are T-siblings, and uiujE(Tp1), by the above paragraph there exists some integer q[], with q<p, such that the rotation eq of σ contains at least one of ui and uj. This contradicts that fact that none of ui,uj occurs in any other rotation of σ other than ep.

Figure 7: Illustration of the statement and the proof of 16.

We are now ready to prove our main lemma.

Lemma 17.

If 𝖽𝗂𝗌𝗍(T,T)k, then there exists an -rotation sequence from T to T, with k, using only vertices in M.

Proof.

Let σ be an -rotation sequence from T to T, for some k, minimizing, among all -rotation sequences from T to T, the number of vertices in V(T)M (that is, the non-marked vertices) used by σ. Note that σ exists by the hypothesis that 𝖽𝗂𝗌𝗍(T,T)k. If there are no vertices in V(T)M used by σ, then we are done, so assume that there are. Our goal is to define another -rotation sequence σ from T to T using strictly less vertices in V(T)M than σ, contradicting the choice of σ and concluding the proof.

To this end, let vV(T)M be a furthest (with respect to the distance to 𝗋𝗈𝗈𝗍(T)) non-marked vertex of T that is used by σ. By 7, we can assume that vB𝖼𝖻. Let Z be the connected component of T[B𝖼𝖻] such that vZ. For technical reasons, it will be helpful to assume that v is not a leaf of Z. (This can be achieved, for instance, by observing that the analysis of the size of the components Z in 7 is not tight. Alternatively, we can just “artificially” increase their diameter by one –i.e., replacing 2k with 2k+1 in the definition of B𝖼𝖻– so that we can safely assume that the leaves of Z are never used by a rotation sequence.) Note that the choice of v as a lowest (i.e., furthest) non-marked vertex of T used by σ implies that for every vertex u𝖼𝗁𝗂𝗅𝖽𝗋𝖾𝗇(T,v), the whole subtree T(u) 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: v has a marked T-sibling v with τ(T,Z,v)=τ(T,Z,v).

Since v is non-marked and by assumption it has some marked T-sibling, the definition of M (namely, that up to k+1 vertices of each type are recursively marked) and 16 imply that v has some marked T-sibling of the same type that is not used by σ. Let without loss of generality v be such a T-sibling of v. Note that the choice of v as a lowest non-marked vertex used by σ implies that the whole subtree T(v) remains intact throughout σ. See Figure 8 for an illustration.

Figure 8: Illustration of Case 1 in the proof of 17. Vertex v is non-marked and used by σ, and its T-sibling v is marked (in red) and not used by σ.

In this case, we define σ from σ by just replacing v with v in all the rotations of σ involving v. 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 T to T. 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 T to T.

Case 2: all T-siblings v of v with τ(T,Z,v)=τ(T,Z,v), if any, are non-marked.

In this case, in order to define another -rotation sequence σ from T to T 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 v with a marked T-sibling of the same type. To this end, the following claim guarantees the existence of a very helpful vertex v. See Figure 9 for an illustration.

Claim 20.

There exists a unique vertex v𝖺𝗇𝖼𝖾𝗌𝗍𝗈𝗋𝗌(Z,v) such that

  • v is non-marked,

  • v has a marked T-sibling v such that

    • τ(T,Z,v)=τ(T,Z,v), and

    • no vertex in T(v) is used by σ, and

  • v is the vertex closest to v satisfying the above properties.

Proof.

Since 𝗋𝗈𝗈𝗍(Z)M and vM, the definition of the marking algorithm implies that there exists a marked T-sibling v of v with τ(T,Z,v)=τ(T,Z,v). Moreover, the fact that M is defined by recursively marking up to k+1 vertices of each type implies, together with 16 and the fact that the desired vertex v is non-marked, that there is some T-sibling v of v with τ(T,Z,v)=τ(T,Z,v) such that no vertex in T(v) is used by σ. Finally, we can clearly choose v in a unique way as being the vertex closest to v satisfying the above properties.

Figure 9: Illustration of Case 2 in the proof of 17. All vertices in T(v) are non-marked, and (at least) vertex v is used by σ. No vertex in T(v) is used by σ, and (at least) vertex v is marked (in red). The sets Ui,τ of vertices used by σ in T(v)Z are depicted with squares, as well as their images in T(v)Z via the representative function ρ.

Note that Case 1 of the proof corresponds to the particular case where v is equal to v 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 T(v) and T(v), starting with v and v, exploiting the definition of types to appropriately define the desired replacement of vertices to construct σ from σ.

Formally, let U be the set of vertices in V(T(v))Z used by σ (so in Case 1, U={v}), and let ρ:UV(T(v))Z be the injective function defined as follows. For i=0,,𝖽𝗂𝗌𝗍T(v,v), let UiU be the set of vertices in V(T(v))Z used by σ that are at distance exactly i from vertex v in T. Note that some of the sets Ui may be empty, and that U𝖽𝗂𝗌𝗍T(v,v) contains v. For every type τ occurring in a vertex in Ui, let Ui,τ be the set of vertices of type τ in Ui. Note that, if a set Ui is non-empty, then {Ui,ττ occurs in Ui} defines a partition of Ui into non-empty sets. Let Ui,τ be a set of marked vertices of type τ in V(T(v))Z of size |Ui,τ| (we shall prove in 21 that it exists). Then we define ρ|Ui,τ as any bijection between Ui,τ and Ui,τ. See Figure 9 for an illustration.

Claim 21 ().

The function ρ is well-defined and injective.

For every vertex uU (recall that U is the set of vertices in V(T(v))Z used by σ), the vertex ρ(u) is called the representative of u. Note that the function ρ is also defined on v, since it is used by σ. We now define σ from σ by replacing, in the rotations defining the sequence, every vertex uU by its representative ρ(u).

Claim 22 ().

σ is a well-defined -rotation sequence.

Claim 23 ().

σ is an -rotation sequence from T to T.

By 23, σ is an -rotation sequence from T to T, and it uses strictly more marked vertices than σ, because no vertex of T(v) is marked (by the conditions in 20), and within T(v) there is at least one marked vertex, namely v. This concludes Case 2.

In both cases, we have defined from σ another -rotation sequence σ from T to T using strictly less vertices in V(T)M than σ, contradicting the choice of σ.

4 Further research

We proved that the Rotation Distance problem, for a general graph G, can be solved in time f(k)|V(G)|, where f(k) is the function given by Theorem 1. This function is quite large, and it is worth trying to improve it. The growth of f(k) 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 v,v have the same type, then for each possible type τ and every integer d at most the bound given in Equation 3, vertices v and v have the same number (up to k+1) of descendants of type τ within distance d. 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 k. So far, this is only known when the considered graph G 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.

Table 1: Known results and open problems about the (parameterized) complexity of the Rotation Distance problem, both on paths and general graphs.
Rotation Distancepathsgeneral graphs𝖭𝖯-hardopen[19]𝖥𝖯𝖳[14, 20, 21, 23, 24] [Theorem 1]Polynomial kernel[14, 24]open

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 k-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 O(3.82k) 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.