Constant factor approximation for the weighted partial degree bounded edge packing problem

In the partial degree bounded edge packing problem (PDBEP), the input is an undirected graph (G=(V,E)) with capacity (c_vin {mathbb {N}}) on each vertex v. The objective is to find a feasible subgraph (G'=(V,E')) maximizing (|E'|), where (G') is said to be feasible if for each (e={u,v}in E'), (deg _{G'}(u)le c_u) or (deg _{G'}(v)le c_v). In the weighted version of the problem, additionally each edge (ein E) has a weight w(e) and we want to find a feasible subgraph (G'=(V,E')) maximizing (sum _{ein E'} w(e)). The problem is already NP-hard if (c_v = 1) for all (vin V) (Zhang in: Proceedings of the joint international conference on frontiers in algorithmics and algorithmic aspects in information and management, FAW-AAIM 2012, Beijing, China, May 14–16, pp 359–367, 2012). In this paper, we introduce a generalization of the PDBEP problem. We let the edges have weights as well as demands, and we present the first constant-factor approximation algorithms for this problem. Our results imply the first constant-factor approximation algorithm for the weighted PDBEP problem, improving the result of Aurora et al. (FAW-AAIM 2013) who presented an (O(log n))-approximation for the weighted case. We also study the weighted PDBEP problem on hypergraphs and present a constant factor approximation if the maximum degree of the hypergraph is bounded above by a constant. We study a generalization of the weighted PDBEP problem with demands where each edge additionally specifies whether it requires at least one, or both its end-points to not exceed the capacity. The objective is to pick a maximum weight subset of edges. We give a constant factor approximation for this problem. We also present a PTAS for the weighted PDBEP problem with demands on H-minor free graphs, if the demands on the edges are bounded by polynomial. We show that the PDBEP problem is APX-hard even for bipartite graphs with (c_v = 1, ; forall vin V) and having degree at most 3.