Next:
GT26 MAXIMUM INDUCED
Up:
Subgraphs and Supergraphs
Previous:
GT24 MINIMUM VERTEX
-
I
NSTANCE
:
Directed or undirected graph
.
-
S
OLUTION
:
A subset
such that the subgraph
has the
property
P
.
-
M
EASURE
:
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 [
239
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997