GT27 M INIMUM V ERTEX D ELETION TO O BTAIN C ONNECTED S UBGRAPH WITH P ROPERTY P

     
• I NSTANCE : Directed or undirected graph .
• S OLUTION : A subset such that the subgraph induced by V-V' is connected and has the property P .
• M EASURE : Cardinality of the set of deleted vertices, i.e., |V'| .

• Bad News: Not approximable within for any if P is any non-trivial hereditary property determined by the blocks (for example planar, outerplanar, bipartite, chordal, cactus, acyclic graph, acyclic digraph, without cycles of specified length, symmetric digraph, antisymmetric digraph) [ 347 ].