Additive approximation for edge-deletion problems

A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following algorithmic problem, called the 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). The first result of this paper states that the edge-deletion problem can be efficiently approximated for any monotone property. • For any fixed ɛ> 0 and any monotone property P, there is a deterministic algorithm, which given a graph G = (V, E) of size n, approximates E ′ P (G) in linear time O(|V | + |E|) to within an additive error of ɛn2. Given the above, a natural question is for which monotone properties one can obtain better additive approximations of E ′ P. Our second main result essentially resolves this problem by giving a precise characterization of the monotone graph properties for which such approximations exist. (1) If there is a bipartite graph that does not satisfy P, then there is a δ> 0 for which it i