MINIMUM VERTEX DELETION TO OBTAIN CONNECTED SUBGRAPH WITH PROPERTY P

• INSTANCE: Directed or undirected graph $G=\left(V,E\right)$.
• SOLUTION: A subset $V' \subseteq V$ such that the subgraph induced by V-V' is connected and has the property P.
• MEASURE: Cardinality of the set of deleted vertices, i.e., $\vert V'\vert$.

  
  

• Bad News: Not approximable within $\vert V\vert^{1-\varepsilon }$ for any $\varepsilon >0$ 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) [470].