Next: MAXIMUM INDUCED CONNECTED SUBGRAPH
Up: Subgraphs and Supergraphs
Previous: MINIMUM VERTEX DELETION TO
  Index
- 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].
Viggo Kann
1999-04-22