Next: MAXIMUM INDUCED CONNECTED SUBGRAPH Up: Subgraphs and Supergraphs Previous: MINIMUM VERTEX DELETION TO Index

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

- INSTANCE: Directed or undirected graph .

- SOLUTION: A subset such that the subgraph has the property P.

- MEASURE: Cardinality of the set of deleted edges, i.e., |E'|.

- Good News: 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].

- Comment: If P is clique, then the problem is approximable within 2, even for the edge weighted version [59].