A Randomised Approximation Algorithm for the Partial Vertex Cover Problem in Hypergraphs

摘要

In this paper we present an approximation algorithm for the k-partial vertex cover problem in hypergraphs. Let H = (V,ε) be a hypergraph with set of vertices V, |V| = n and set of (hyper-)edges |ε|,|ε| = m. The k-partial vertex cover problem in hypergraphs is the problem of finding a minimum cardinality subset of vertices in which at least k hyperedges are incident. It is a generalisation of the fundamental (partial) vertex cover problem in graphs and the hitting set problem in hypergraphs. Let l,l ≥ 2 be the maximum size of an edge, Δ be the maximum vertex degree and D be maximum edge degree. For a constant l,l ≥ 2 a non-approximabilty result is known: an approximation ratio better than l cannot be achieved in polynomial-time under the unique games conjecture (Khot and Rageev 2003, 2008). On the other hand, with the primal-dual method (Gandhi, Khuller, Srinivasan 2001) and the local-ratio method (Bar-Yehuda 2001), the l-approximation ratio can be proved. Thus approximations below the Z-ratio for large classes of hypergraphs, for example those with constant D or Δ are interesting. In case of graphs (I = 2) such results are known. In this paper we break the l-approximation barrier for hypergraph classes with constant D resp. Δ for the partial vertex cover problem in hypergraphs. We propose a randomised algorithm of hybrid type which combines LP-based randomised rounding and greedy repairing. For hypergraphs with arbitrary l, l ≥ 3, and constant D the algorithm achieves an approximation ratio of l(1 - Ω(1/(D +1))), and this can be improved to l(1 - Ω(1/Δ)) if A is constant and k ≥ m/4. For the class of l-uniform hypergraphs with both l and Δ being constants and l ≤ 4Δ, we get a further improvement to a ratio of l (1 - l-1/4Δ). The analysis relies on concentration inequalities and combinatorial arguments.