An improved kernel size for rotation distance in binary trees

Kernelization is one technique for studying intractable problems. By pre-processing a problem instance, and converting it into an equivalent smaller instance, one can substantially lower the time needed to obtain a solution. Cleary and St. John first established the fixed-parameter tractability of the problem of determining whether two binary trees are within a distance of k rotations of each other. They showed that the original two trees can be reduced to an equivalent pair of trees each containing at most 5k nodes. In this paper we show an improved bound on the size of the kernel. Using the equivalence of binary trees and convex polygon triangulations, we show that the kernel size is bounded by 2k.