GT26 M AXIMUM I NDUCED C ONNECTED S UBGRAPH WITH P ROPERTY P

               
• I NSTANCE : Graph .
• S OLUTION : A subset such that the subgraph induced by V' is connected and has the property P .
• M EASURE : 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) [ 263 ].
• Comment: NPO PB-complete when P is either path or chordal [ 49 ]. NPO PB-complete and not approximable within for any when P is simple cycle [ 203 ].

                     

• Garey and Johnson: GT22 and GT23