
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2010  Copyright 2010 Universität Bonn, Institut für Informatik, Abt. V  
85318 12.12.2010 
Approximating Vertex Cover in Dense Hypergraphs
Jean Cardinal, Marek Karpinski, Richard Schmied and Claus Viehmann [Download PostScript] [Download PDF] 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 kapproximations, 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 polynomialtime algorithm with approximation factor k / (1+(k1) d / (kΔ)), where d and Δ are the average and maximum degree, respectively, and Δ must be Ω(n^{k1} / 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 / (21 / k) for subdense regular hypergraphs, which is shown to be the best possible under the unique games conjecture. 

Last Change:
11/05/14 at 10:52:08
English 
Universität Bonn > Institut für Informatik > Abteilung V 