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