Approximating Vertex Cover in Dense Hypergraphs

Details Approximating Vertex Cover in Dense Hypergraphs Approximating Vertex Cover in Dense Hypergraphs

2010-12-12

arxiv.org/abs/1012.2573v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider the minimum vertex cover problem in hypergraphs in which every hyperedge has size k (also known as minimum hitting set problem, or minimum set cover with element frequency k). Simple algorithms exist that provide k-approximations, and this is believed to be the best possible approximation achievable in polynomial time. We show how to exploit density and regularity properties of the input hypergraph to break this barrier. In particular, we provide a randomized polynomial-time algorithm with approximation factor k/(1 +(k-1)d/(k Delta)), where d and Delta are the average and maximum degree, respectively, and Delta must be Omega(n^{k-1}/log n). The proposed algorithm generalizes the recursive sampling technique of Imamura and Iwama (SODA'05) for vertex cover in dense graphs. As a corollary, we obtain an approximation factor k/(2-1/k) for subdense regular hypergraphs, which is shown to be the best possible under the unique games conjecture.

Affiliated with

Also associated with

No associations

Rating

Approximating Vertex Cover in Dense Hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximating Vertex Cover in Dense Hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating Vertex Cover in Dense Hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-637556