Next:
GT25 MINIMUM EDGE
Up:
Subgraphs and Supergraphs
Previous:
GT23 MAXIMUM INDUCED
-
I
NSTANCE
:
Directed or undirected graph
.
-
S
OLUTION
:
A subset
such that the subgraph induced by
V-V'
has the
property
P
.
-
M
EASURE
:
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) [
263
].
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 [
239
].
-
Bad News:
A
PX
-hard for any non-trivial hereditary property
P
[
263
].
-
Comment:
It is approximable within
if the subgraph has to be
bipartite [
127
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997