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].
.
such that the subgraph induced by V-V' has the
property P.
.
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].