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.)

$\endgroup$
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.

$\endgroup$
  • $\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 '15 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 '15 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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