Next: MAXIMUM COMMON POINT SET Up: Compression and Representation Previous: LONGEST COMMON SUBSEQUENCE Index

### MAXIMUM COMMON SUBTREE

- INSTANCE: Collection of trees.

- SOLUTION: A tree T' isomorphic to a subtree (i.e. induced connected subgraph) of each Ti.

- MEASURE: Size, i.e. number of nodes, of the common subtree T'.

- Good News: Approximable within , where n is the size of the smallest Ti [7].

- Bad News: Not approximable within for any [7].

- Comment: Transformation from MAXIMUM INDEPENDENT SET. hardness holds for the variation where the nodes are labeled and where maximum degree is bounded by a constant . Approximable within when the maximum degree is constant. Variation in which the nodes are labeled is approximable within if the number of distinct labels is O(logO(1)n) and within in general [7]. Approximable within 2 if the solution is an isomorphic edge subset of each tree. APX-hard when the number of input trees is a constant at least 3, but polynomial-time solvable if the maximum degree is additionally bounded by constant or for only two trees [6].

Next: MAXIMUM COMMON POINT SET Up: Compression and Representation Previous: LONGEST COMMON SUBSEQUENCE Index