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.