- INSTANCE:
Trees
and
with labels on the nodes.
- SOLUTION:
A common embedded sub-tree, i.e. a labeled tree
*T'*that can be embedded into both and . An embedding from*T'*to*T*is an injective function from the nodes of*T'*to the nodes of*T*that preserves labels and ancestorship. Note that since fathership does not need to be preserved,*T'*does not need to be an ordinary subtree. - MEASURE:
Cardinality of the common embedded sub-tree, i.e., .

*Good News:*Approximable within , where*n*is the number of nodes in the trees [230].*Bad News:*APX-hard [475].*Comment:*Transformation from MAXIMUM*K*-SET PACKING. Variation in which the problem is to minimize the edit distance between the two trees is also APX-hard.