Finding a minimum tree which is isomorphic to a subtree of $T_1$ but not to a subtree of $T_2$ Consider the problem that receives two trees $T_1$, $T_2$, and asks to find a minimum size tree $T$ such that there exists a subtree of $T_1$ which is isomorphic to $T$, but there is no such isomorphic subtree in $T_2$.


  What is known about the complexity of this problem?
You can put a tree into a cannonical form in $O(n)$ with leaf contractions. Read, Ronald C. (1972), "The coding of various kinds of unlabeled trees", Graph Theory and Computing, Academic Press, New York, pp. 153–182

When $T_{1}$ and $T_{2}$ are isomorphic you can solve it in $O(n)$.

Shamir's paper has $O({k^{1.5}\over log\ k}n)$ for testing if one tree is a subtree of the other, https://www.cs.bgu.ac.il/~dekelts/publications/subtree.pdf 

Not sure if that helps.