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].