- INSTANCE: Directed or undirected graph .
- SOLUTION:
A subset
such that the subgraph induced by
*V-V'*has the property*P*. - MEASURE:
Cardinality of the set of deleted vertices, i.e., .

*Good News:*Approximable within some constant for any hereditary property*P*with a finite number of minimal forbidden subgraphs (for example transitive digraph, symmetric, antisymmetric, tournament, line graph, and interval) [364]. Approximable within some constant for any property*P*that can be expressed as a universal first order sentence over subsets of edges of the graph [330].*Bad News:*APX-hard for any non-trivial hereditary property*P*[364].*Comment:*Approximable within if the subgraph has to be bipartite [188]. Approximable within some constant factor for any ``matroidal'' property*P*and under simple and natural weighting schemes [177].