MINIMUM EDGE DELETION TO OBTAIN SUBGRAPH WITH PROPERTY P

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

INSTANCE: Directed or undirected graph $G=\left(V,E\right)$ .
SOLUTION: A subset $E'\subseteq E$ such that the subgraph $G=\left(V,E-E'\right)$ has the property P.
MEASURE: Cardinality of the set of deleted edges, i.e., $\vert E'\vert$ .
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 [330].
Comment: If P is clique, then the problem is approximable within 2, even for the edge weighted version [60].

Viggo Kann
2000-03-20