** Next:** MAXIMUM DEGREE-BOUNDED CONNECTED SUBGRAPH
** Up:** Subgraphs and Supergraphs
** Previous:** MAXIMUM INDUCED CONNECTED SUBGRAPH
** Index**

- INSTANCE:
Directed or undirected graph
.
- SOLUTION:
A subset
such that the subgraph induced by
*V-V'* is
connected and has the property *P*.
- MEASURE:
Cardinality of the set of deleted vertices, i.e., .

*Bad News:*
Not approximable within
for any
if *P*
is any non-trivial hereditary property determined by the blocks (for example
planar, outerplanar, bipartite, chordal, cactus, acyclic graph, acyclic
digraph, without cycles of specified length, symmetric digraph,
antisymmetric digraph)
[470].

*Viggo Kann*

*2000-03-20*