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

### MINIMUM VERTEX DELETION TO OBTAIN CONNECTED SUBGRAPH WITH PROPERTY P

- 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., |V'|.

- 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) [447].