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