Thursday April 13th at 4pm

In this talk we consider the following edge-deletion problem; given a monotone

property P and a graph

in order to turn

Our first result states that for any monotone graph property P, any

Our second main result shows that such approximation is essentially best possible

and for most properties, it is NP-hard to approximate

error of

The proof requires several new ideas and involves tools from Extremal Graph Theory

together with spectral techniques. Interestingly, prior to this work it was not even

known that computing

NP-hard. We thus answer (in a strong form) a question of Yannakakis raised in 1981.

Joint work with N. Alon and A. Shapira.