# Additive Approximation for Edge-Deletion Problems

 COMPUTER SCIENCE/DISCRETE MATH, II Topic: Additive Approximation for Edge-Deletion Problems Speaker: Noga Alon Affiliation: IAS Date: Tuesday, April 19 Time/Room: 10:30am - 12:30pm/S-101

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.