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

Pawan Aurora (), Sumit Singh () and Shashank K. Mehta ()
Additional contact information
Pawan Aurora: Indian Institute of Technology
Sumit Singh: Indian Institute of Technology
Shashank K. Mehta: Indian Institute of Technology

Journal of Combinatorial Optimization, 2016, vol. 32, issue 1, No 10, 159-173

Abstract: Abstract 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.

Keywords: Edge-packing problems; Approximation algorithm; Iterative rounding; Lagrangian relaxation (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9868-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:1:d:10.1007_s10878-015-9868-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9868-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().