MAXIMUM INDUCED CONNECTED SUBGRAPH WITH PROPERTY P

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

INSTANCE: Graph $G=\left(V,E\right)$ .
SOLUTION: A subset $V' \subseteq V$ such that the subgraph induced by V' is connected and has the property P.
MEASURE: Cardinality of the induced connected subgraph, i.e., $\vert V'\vert$ .
Bad News: Not approximable within $\vert V\vert^{1-\varepsilon }$ for any $\varepsilon >0$ 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 $\vert V\vert^{1-\varepsilon }$ for any $\varepsilon >0$ when P is simple cycle [285].
Garey and Johnson: GT22 and GT23

Viggo Kann
2000-03-20