The Bounded Degree Deletion problem with degree bound b : V → Z_+ (denoted b-BDD), is that of computing a minimum cost vertex set in a graph G = (V, E) such that, when it is removed from G, the degree of any remaining vertex v is no larger than b(v). It will be shown that b-BDD can be approximated within max{2, b/2 + 1}, improving the previous best bound for 2 ≤ b ≤ 5, where b is the maximum degree bound, i.e., b = max{b(v) v ∈ V}. The new bound is attained by casting b-BDD as the vertex deletion problem for such a property inducing a 2-polymatroid on the edge set of a graph, and then reducing it to the submodular set cover problem.
展开▼
