<p>It's fixed-parameter tractable in the natural parameter, the distance. So if two trees have distance $k$ you can find the distance in time polynomial + $f(k)$ for some function $f$. The proof is a kernelization that produces a kernel of size $O(k)$ so putting that together with the naive method of finding a shortest path in the flip graph gives time singly exponential in $k$. See "Rotation distance is fixed-parameter tractable", Cleary &amp; St. John, <em>Inf. Proc. Lett.</em> 2009, and "An improved kernel size for rotation distance in binary trees", Lucas, <em>Inf. Proc. Lett.</em> 2010. See also "A linear-time approximation for rotation distance", Cleary &amp; St. John, <em>JGAA</em> 2010.</p>

CC BY-SA 3.0
2015-11-20T08:23:58.450Z
If you don't mind, consulting http://arxiv.org/abs/0903.0197 I see that they assert that the kernelization can be done in linear time in $n$, yielding roughly $O(n)+4^{7k}$ (even for my version of the problem, since the kernelization and solution algorithm do not depend on $k$). The part I don't get is why the kernelization is linear - is it really so easy to recognize common subtrees and chains?
Mario Carneiro
CC BY-SA 3.0
2015-11-21T00:21:18.757Z
It's not difficult to find the set of nodes that belong to matching subtrees in linear time, by doing a postorder traversal of both trees simultaneously. A node is part of a matching subtree if and only if all its children are also part of matching subtrees (already computed because of the postorder ordering) and the corresponding node in the other tree has its children in the same positions in the postorder.
David Eppstein
CC BY-SA 3.0
2015-11-20T06:54:19.673Z
2015-11-20T06:54:19.673Z
David Eppstein
<p>What is the fastest known algorithm(s) for finding a minimal sequence of <a href="https://en.wikipedia.org/wiki/Tree_rotation" rel="nofollow">tree rotations</a> that transform given trees $A$ to $B$ (each with $n$ unlabeled nodes)? Equivalently, how can we find a shortest path between two elements in the <a href="https://en.wikipedia.org/wiki/Tamari_lattice" rel="nofollow">Tamari lattice</a>? Since Wikipedia lists the problem of finding the length of such a path as not known to be in polynomial time, presumably the best known algorithm is $O(c^n)$.</p>

<p>As a rough attempt at an upper bound, the Tamari lattice has $C_n$ nodes (Catalan's number), and by its definition each has degree $n-1$ (for the rotations of each of its internal nodes), while the diameter of the graph is at most $2n-2$, so an algorithm of <a href="https://en.wikipedia.org/wiki/Shortest_path_problem#Directed_graphs_with_nonnegative_weights" rel="nofollow">Johnson 1982</a> for shortest paths yields an $O(C_nn\log\log n)$, or $4^{n-o(n)}$ upper bound.</p>

<p>(I would also be interested to know about polynomial time algorithms that find approximate solutions, for example with length $\le c\ell$ where $\ell$ is the shortest path.)</p>

<cc.complexity-theory><graph-algorithms><lattice><binary-trees>
Algorithms for tree rotation
Mario Carneiro
# Algorithms for tree rotation

(Asked by: username_0 on 2015-11-20)

What is the fastest known algorithm(s) for finding a minimal sequence of [tree rotations](https://en.wikipedia.org/wiki/Tree_rotation) that transform given trees $A$ to $B$ (each with $n$ unlabeled nodes)? Equivalently, how can we find a shortest path between two elements in the [Tamari lattice](https://en.wikipedia.org/wiki/Tamari_lattice)? Since Wikipedia lists the problem of finding the length of such a path as not known to be in polynomial time, presumably the best known algorithm is $O(c^n)$.

As a rough attempt at an upper bound, the Tamari lattice has $C\_n$ nodes (Catalan's number), and by its definition each has degree $n-1$ (for the rotations of each of its internal nodes), while the diameter of the graph is at most $2n-2$, so an algorithm of [Johnson 1982](https://en.wikipedia.org/wiki/Shortest_path_problem#Directed_graphs_with_nonnegative_weights) for shortest paths yields an $O(C\_nn\log\log n)$, or $4^{n-o(n)}$ upper bound.

(I would also be interested to know about polynomial time algorithms that find approximate solutions, for example with length $\le c\ell$ where $\ell$ is the shortest path.)

**Tags:** cc.complexity-theory, graph-algorithms, lattice, binary-trees


---

## 1 answers

### Answer by username_1 on 2015-11-20. Score: 7 | Accepted answer

It's fixed-parameter tractable in the natural parameter, the distance. So if two trees have distance $k$ you can find the distance in time polynomial + $f(k)$ for some function $f$. The proof is a kernelization that produces a kernel of size $O(k)$ so putting that together with the naive method of finding a shortest path in the flip graph gives time singly exponential in $k$. See "Rotation distance is fixed-parameter tractable", Cleary & St. John, *Inf. Proc. Lett.* 2009, and "An improved kernel size for rotation distance in binary trees", Lucas, *Inf. Proc. Lett.* 2010. See also "A linear-time approximation for rotation distance", Cleary & St. John, *JGAA* 2010.

> **Comments:**
> **username_0**: If you don't mind, consulting http://arxiv.org/abs/0903.0197 I see that they assert that the kernelization can be done in linear time in $n$, yielding roughly $O(n)+4^{7k}$ (even for my version of the problem, since the kernelization and solution algorithm do not depend on $k$). The part I don't get is why the kernelization is linear - is it really so easy to recognize common subtrees and chains?  
> **username_1**: It's not difficult to find the set of nodes that belong to matching subtrees in linear time, by doing a postorder traversal of both trees simultaneously. A node is part of a matching subtree if and only if all its children are also part of matching subtrees (already computed because of the postorder ordering) and the corresponding node in the other tree has its children in the same positions in the postorder.  

---

