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

*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) [364].*Comment:*NPO PB-complete when*P*is either path or chordal [77]. NPO PB-complete and not approximable within for any when*P*is simple cycle [285].*Garey and Johnson:*GT22 and GT23