Next: MINIMUM GRAPH TRANSFORMATION
Up: Iso- and Other Morphisms
Previous: MAXIMUM COMMON INDUCED SUBGRAPH
  Index
- 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.
Viggo Kann
1999-04-22