MINIMUM VERTEX DELETION TO OBTAIN 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' has the property P.
• MEASURE: Cardinality of the set of deleted vertices, i.e., $\vert V'\vert$.

  
  

• Good News: Approximable within some constant for any hereditary property P with a finite number of minimal forbidden subgraphs (for example transitive digraph, symmetric, antisymmetric, tournament, line graph, and interval) [364]. Approximable within some constant for any property P that can be expressed as a universal first order sentence over subsets of edges of the graph [330].
• Bad News: APX-hard for any non-trivial hereditary property P [364].
• Comment: Approximable within $O(\log \vert V\vert)$ if the subgraph has to be bipartite [188]. Approximable within some constant factor for any ``matroidal'' property P and under simple and natural weighting schemes [177].