Next: MINIMUM VERTEX DELETION TO Up: Subgraphs and Supergraphs Previous: MINIMUM EDGE DELETION TO Index

### MAXIMUM INDUCED CONNECTED SUBGRAPH WITH PROPERTY P

- 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