3
$\begingroup$

What is the fastest known algorithm(s) for finding a minimal sequence of tree rotations 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? 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 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.)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ If you don't mind, consulting 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? $\endgroup$
    – Mario Carneiro
    Nov 20, 2015 at 8:23
  • $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Nov 21, 2015 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.