The edge-deletion problem can be approximated in linear time

Combinatorics, Mathematics of Computation 1 Minute

You need to know: Basic graph theory, bipartite graph, deterministic algorithm, approximation algorithm, running time of an algorithm, NP-hard problem, big O notation.

Background: A graph property is monotone if it is closed under removal of vertices and edges. The edge-deletion problem is: given a monotone property P and a graph G, compute the smallest number E_P(G) of edge deletions that are needed in order to turn G into a graph satisfying P.

The Theorem: On 7th July 2005, Noga Alon, Asaf Shapira, and Benny Sudakov submitted to the Annals of Mathematics a paper in which they proved the following result. For any fixed \epsilon>0 and any monotone property P, there is a deterministic algorithm which, given a graph G with n vertices and m edges, approximates E_P(G) in linear time O(n+m) to within an additive error of \epsilon n^2. On the other hand, if all bipartite graphs satisfy P, then for any fixed \delta>0 it is NP-hard to approximate E_P(G) to within an additive error of n^{2-\delta}.

Short context: How many edges we need to remove from a given graph G to make it, for example, triangle-free, or 3-colourable? The Theorem states that we can quickly solve any such problem approximately with error \epsilon n^2 but not with error n^{2-\delta} for any \delta>0. Before 2005, \epsilon n^2 approximation algorithm was not known even for triangle-free property, and the NP-hardness result was not known even for computing E_P(G) exactly.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 9.7 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment