Next: MINIMUM EDGE DELETION TO Up: Subgraphs and Supergraphs Previous: MAXIMUM INDUCED SUBGRAPH WITH Index

### MINIMUM VERTEX DELETION TO OBTAIN SUBGRAPH WITH PROPERTY P

- INSTANCE: Directed or undirected graph .

- SOLUTION: A subset such that the subgraph induced by V-V' has the property P.

- MEASURE: Cardinality of the set of deleted vertices, i.e., |V'|.

- 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) [345]. 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 [313].
- Bad News: APX-hard for any non-trivial hereditary property P [345].

- Comment: Approximable within if the subgraph has to be bipartite [176]. Approximable within some constant factor for any ``matroidal'' property P and under simple and natural weighting schemes [165].