Next: MINIMUM EQUIVALENT DIGRAPH
Up: Subgraphs and Supergraphs
Previous: MINIMUM EDGE 2-SPANNER
  Index
- INSTANCE:
Graph
.
- SOLUTION:
A subset
such that the induced subgraph
is
k-colorable, i.e., there is a coloring for G' of cardinality at most k.
- MEASURE:
Cardinality of the vertex set of the induced subgraph, i.e., |V'|.
- Good News:
As easy to approximate as MAXIMUM INDEPENDENT SET for
(finding k
independent sets)
[208].
- Bad News:
As hard to approximate as MAXIMUM INDEPENDENT SET for
[368].
- Comment:
Transformation from MAXIMUM INDEPENDENT SET.
Equivalent to MAXIMUM INDEPENDENT SET for k=1.
Admits a PTAS for planar graphs [50].
Admits a PTAS for `
-near-planar' instances for any
[248].
The case of degrees bounded by
,
for
is
approximable within (B/k + 1)/2 [209] and
APX-complete.
Viggo Kann
1999-04-22