Partial Degree Bounded Edge Packing Problem with Arbitrary Bounds

摘要

Given a graph G = (V, E) and a non-negative integer c_u for each u ∈ V. Partial Degree Bounded Edge Packing (PDBEP) problem is to find a subgraph G' = (V, E') with maximum |E'| such that for each edge (u, v) ∈ E', either degG'(u) ≤ c_u or degG'(v) ≤ c_v. The problem has been shown to be NP-hard even for uniform degree constraint (i.e., all c_u being equal). Approximation algorithms for uniform degree cases with c_u equal to 1 and 2 with approximation ratio of 2 and 32/11 respectively are known. In this work we study general degree constraint case (arbitrary degree constraint for each vertex) and present two combinatorial approximation algorithms with approximation factors 4 and 2. We also study a related integer program for which we present an iterative rounding algorithm with approximation factor 1.5/(1 - ε) for any positive e. This also leads to a 3/(1 - ε)~2 factor approximation algorithm for the general PDBEP problem. For special cases (large values of c_v/degG(v)'s) the factor improves up to 1.5/(1 - ε). Next we study the same problem with weighted edges. In this case we present a 2 + log_2 n approximation algorithm. In the literature exact O(n~2) complexity algorithm for trees is known in case of uniform degree constraint. We improve this result by giving an O(n · log n) complexity exact algorithm for trees with general degree constraint.