SR7 M AXIMUM C OMMON S UBTREE

     
• I NSTANCE : Collection of trees.
• S OLUTION : A tree T' isomorphic to a subtree (i.e. induced connected subgraph) of each .
• M EASURE : Size, i.e. number of nodes, of the common subtree T' .

• Good News: Approximable within , where n is the size of the smallest [ 218 ].
• Bad News: Not approximable within for some [ 3 ].
• Comment: Transformation from M AXIMUM I NDEPENDENT S ET . Hardness holds also for the variations where the nodes are labeled, where maximum degree is bounded by a constant , and where the tree is rooted and the solution must contain the root [ 3 ]. Approximable within when the maximum degree is constant [ 218 ]. Variation in which the nodes are labeled is approximable within if the number of distinct labels is [ 218 ] and within in general [ 3 ]. Approximable within 2 if the solution is an isomorphic edge subset of each tree. A PX -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 [ 3 ].