MAXIMUM INDUCED CONNECTED SUBGRAPH WITH PROPERTY P

• 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