Next: MAXIMUM DEGREE-BOUNDED CONNECTED SUBGRAPH
Up: Subgraphs and Supergraphs
Previous: MAXIMUM INDUCED CONNECTED SUBGRAPH
Directed or undirected graph
such that the subgraph induced by V-V' is
connected and has the property P.
Cardinality of the set of deleted vertices, i.e., .
- Bad News:
Not approximable within
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,