| 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.