A graph property is monotone if it is closed under removal of vertices and edges. We consider the following algorithmic problem, called the edge-deletion problem; given a monotone property P and a graph G, compute the smallest number of edge deletions that are needed in order to turn G into a graph satisfying P. We denote this quantity by E′ _P (G). Our first result states that the edge-deletion problem can be efficiently approximated for any monotone property.