- INSTANCE:
Collection
of trees.
- SOLUTION:
A tree
*T'*isomorphic to a subtree (i.e. induced connected subgraph) of each . - MEASURE:
Size, i.e. number of nodes, of the common subtree
*T'*.

*Good News:*Approximable within , where*n*is the size of the smallest [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 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].