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

*Good News:*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].*Comment:*If P is clique, then the problem is approximable within 2, even for the edge weighted version [60].