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)$$ G = ( V , E ) with capacity $$c_v\in {\mathbb {N}}$$ c v ∈ N on each vertex v. The objective is to find a feasible subgraph $$G'=(V,E')$$ G ′ = ( V , E ′ ) maximizing $$|E'|$$ | E ′ | , where $$G'$$ G ′ is said to be feasible if for each $$e=\{u,v\}\in E'$$ e = { u , v } ∈ E ′ , $$\deg _{G'}(u)\le c_u$$ deg G ′ ( u ) ≤ c u or $$\deg _{G'}(v)\le c_v$$ deg G ′ ( v ) ≤ c v . In the weighted version of the problem, additionally each edge $$e\in E$$ e ∈ E has a weight w(e) and we want to find a feasible subgraph $$G'=(V,E')$$ G ′ = ( V , E ′ ) maximizing $$\sum _{e\in E'} w(e)$$ ∑ e ∈ E ′ w ( e ) . The problem is already NP-hard if $$c_v = 1$$ c v = 1 for all $$v\in V$$ v ∈ 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)$$ 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 v\in V$$ c v = 1 , ∀ v ∈ V and having degree at most 3.