A new approach for approximating node deletion problems

We present a new approach for approximating node deletion problems by combining the local ratio and the greedy multicovering algorithms. For a function , our approach allows to design a 2+max_v∈V(G)logf(v) approximation algorithm for the problem of deleting a minimum number of nodes so that the degree of each node v in the remaining graph is at most f(v). This approximation ratio is shown to be asymptotically optimal. The new method is also used to design a 1+(log2)(k−1) approximation algorithm for the problem of deleting a minimum number of nodes so that the remaining graph contains no k-bicliques.