MAXIMUM COMMON EMBEDDED SUB-TREE

• INSTANCE: Trees $T_1$ and $T_2$ with labels on the nodes.

• SOLUTION: A common embedded sub-tree, i.e. a labeled tree T' that can be embedded into both $T_1$ and $T_2$. 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., $\vert T'\vert$.

  
  

• Good News: Approximable within $\log^2 n$, 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.