Discrete Mathematics and Optimization Seminar

---

Benny Sudakov
Princeton University and IAS
Thursday April 13th at 4pm
McConnell 320



Title. Additive Approximation for Edge-Deletion Problems.

Abstract. A graph property is monotone if it is closed under removal of vertices and edges.
In this talk we consider the following edge-deletion problem; given a monotone
property P and a graph G, compute the smallest number of edge deletions that are needed
in order to turn G into a graph satisfying P. We denote this quantity by E_P(G).
Our first result states that for any monotone graph property P, any \epsilon >0 and
n-vertex input graph G one can approximate E_P(G) up to an additive error of \epsilon n^2.

Our second main result shows that such approximation is essentially best possible
and for most properties, it is NP-hard to approximate E_P(G) up to an additive
error of n^{2-\delta}, for any fixed positive \delta.
The proof requires several new ideas and involves tools from Extremal Graph Theory
together with spectral techniques. Interestingly, prior to this work it was not even
known that computing E_P(G) precisely for dense monotone properties is
NP-hard. We thus answer (in a strong form) a question of Yannakakis raised in 1981.
Joint work with N. Alon and A. Shapira.