Next: MINIMUM EDGE DELETION TO
Up: Subgraphs and Supergraphs
Previous: MAXIMUM INDUCED SUBGRAPH WITH
  Index
- 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., |V'|.
- 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) [345].
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 [313].
- Bad News:
APX-hard for any non-trivial hereditary property P
[345].
- Comment:
Approximable within
if the subgraph has to be
bipartite [176].
Approximable within some constant factor for any ``matroidal'' property
P and under simple and natural weighting schemes [165].
Viggo Kann
1999-04-22