Next: MINIMUM VERTEX DELETION TO
Up: Subgraphs and Supergraphs
Previous: MINIMUM EDGE DELETION TO
  Index
- INSTANCE:
Graph
.
- SOLUTION:
A subset
such that the subgraph induced by V' is connected
and has the property P.
- MEASURE:
Cardinality of the induced connected subgraph, i.e., |V'|.
- Bad News:
Not approximable within
for any
if P is a non-trivial hereditary graph property that
is satisfied by all paths and is false for some complete bipartite graph
(for example path, tree, planar, outerplanar, bipartite, chordal, interval)
[345].
- Comment:
NPO PB-complete when P is either path or chordal [71].
NPO PB-complete and not approximable within
for any
when P is simple cycle [270].
- Garey and Johnson: GT22 and GT23
Viggo Kann
1999-04-22