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.