Next: MINIMUM GRAPH TRANSFORMATION Up: Iso- and Other Morphisms Previous: MAXIMUM COMMON INDUCED SUBGRAPH Index

### MAXIMUM COMMON EMBEDDED SUB-TREE

- INSTANCE: Trees T1 and T2 with labels on the nodes.

- SOLUTION: A common embedded sub-tree, i.e. a labeled tree T' that can be embedded into both T1 and T2. 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., |T'|.

- Good News: Approximable within , where n is the number of nodes in the trees [214].

- Bad News: APX-hard [451].

- 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.