MAXIMUM COMMON SUBTREE

• INSTANCE: Collection $T_1, \ldots, T_n$ of trees.

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

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

  
  

• Good News: Approximable within $O(\log\log n/\log^2 n)$, where n is the size of the smallest $T_i$ [7].

• Bad News: Not approximable within $n^{1/4-\varepsilon }$ for any $\varepsilon >0$ [7].

• Comment: Transformation from MAXIMUM INDEPENDENT SET. $n^{1-\varepsilon }$ hardness holds for the variation where the nodes are labeled and where maximum degree is bounded by a constant $B \ge 3$. Approximable within $O(n/\log^2 n)$ when the maximum degree is constant. Variation in which the nodes are labeled is approximable within $O(\log\log n/\log^2 n)$ if the number of distinct labels is $O(log^{O(1)}n)$ and within $O(n/\log n)$ 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].