The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees (Q1962070)

It is known that the following question is NP-complete: Given a set of trees with leaves labelled from the set \(L\), does there exist a tree \(T\) with leaves labelled by \(L\) such that each of the given trees is homeomorphic to a subtree of \(T\)? If all trees have one label in common the question is solvable in polynomial time. The authors prove, however, that the problem is NP-complete even if it is known that each given tree contains \(x\) or \(y\), where \(x\) and \(y\) are two given labels. Some related complexity results are proved, too.