Next: MINIMUM VERTEX DELETION TO
Up: Subgraphs and Supergraphs
Previous: MAXIMUM INDEPENDENT SEQUENCE
  Index
- INSTANCE:
Graph
.
The property P must be hereditary, i.e., every subgraph of G' satisfies
P whenever G' satisfies P, and non-trivial, i.e., it is satisfied
for infinitely many graphs and false for infinitely many graphs.
- SOLUTION:
A subset
such that the subgraph induced by V' has the
property P.
- MEASURE:
Cardinality of the induced subgraph, i.e., .
- Good News:
Approximable within
[224].
- Bad News:
Not approximable within
for some
unless P=NP, if P is false for some clique or independent set (for
example planar, outerplanar, bipartite, complete bipartite, acyclic,
degree-constrained, chordal, interval).
Not approximable within
for any
unless NPQP, if P is a non-trivial
hereditary graph property (for example comparability, permutation, perfect,
circular-arc, circle, line graph) [364].
- Comment:
Approximable within
if
P is false for some clique or independent set
[224], and approximable within
where
is the maximum degree [218].
All these good news are valid also for the vertex weighted version
[224].
The same problem on directed graphs is not approximable within
for any
unless
NPQP, if P is a non-trivial hereditary digraph property
(for example acyclic, transitive, symmetric, antisymmetric, tournament,
degree-constrained, line digraph)
[364].
Admits a PTAS for planar graphs if P is hereditary and determined
by the connected components, i.e., G' satisfies P whenever every
connected component of G' satisfies P
[386].
Admits a PTAS for -free or -free graphs if P is hereditary [108].
- Garey and Johnson: GT21
Next: MINIMUM VERTEX DELETION TO
Up: Subgraphs and Supergraphs
Previous: MAXIMUM INDEPENDENT SEQUENCE
  Index
Viggo Kann
2000-03-20