Computer Science/Discrete Mathematics Seminar II

I will sketch a proof that for any monotone graph property P and any $\epsilon >0$ one can approximate efficiently the minimum number of edges that have to be deleted from an n-vertex input graph to get a graph that satisfies P, up to an additive error of $\epsilon n^2$. Moreover, for any dense monotone property, that is, a property for which there are graphs on n vertices with $\Omega (n^2)$ edges that satisfy it, it is NP-hard to approximate this minimum up to an additive error of $n^{2-\epsilon}$, for any fixed positive $\epsilon$. The second part answers a question raised by Yannakakis in 1981. Joint work with A. Shapira and B. Sudakov.