View article

Given two rooted, labeled, and unordered trees, we consider the problem of finding the largest common sub-tree and the problem of finding the edit distance between them. We show that both problems are MAX SNP-hard. This means that neither problem has a polynomial time approximation scheme (PTAS) unless P = NP.