Next: MAXIMUM EDGE SUBGRAPH
Up: Subgraphs and Supergraphs
Previous: MAXIMUM K-COLORABLE SUBGRAPH
  Index
- INSTANCE:
Tree
and a set of trees H.
- SOLUTION:
A subset
such that the subgraph
does not contain any subtree isomorphic to a tree from H.
- MEASURE:
Cardinality of the subgraph, i.e., |E'|.
- Good News:
Admits a PTAS [415].
Viggo Kann
1999-04-22