Partial degree bounded edge packing problem for graphs and $$k$$ k -uniform hypergraphs

Given a graph $$G=(V,E)$$ G = ( V , E ) and a non-negative integer $$c_u$$ c u for each $$u\in V$$ u ∈ V , partial degree bounded edge packing problem is to find a subgraph $$G^{\prime }=(V,E^{\prime })$$ G ′ = ( V , E ′ ) with maximum $$|E^{\prime }|$$ | E ′ | such that for each edge $$(u,v)\in E^{\prime }$$ ( u , v ) ∈ E ′ , either $$deg_{G^{\prime }}(u)\le c_u$$ d e g G ′ ( u ) ≤ c u or $$deg_{G^{\prime }}(v)\le c_v$$ d e g G ′ ( v ) ≤ c v . The problem has been shown to be NP-hard even for uniform degree constraint (i.e., all $$c_u$$ c u being equal). In this work we study the general degree constraint case (arbitrary degree constraint for each vertex) and present two combinatorial approximation algorithms with approximation factors $$4$$ 4 and $$2$$ 2 . Then we give a $$\log _2 n$$ log 2 n approximation algorithm for edge-weighted version of the problem and an efficient exact algorithm for edge-weighted trees with time complexity $$O(n\log n)$$ O ( n log n ) . We also consider a generalization of this problem to $$k$$ k -uniform hypergraphs and present a constant factor approximation algorithm based on linear programming using Lagrangian relaxation.