A randomised approximation algorithm for the hitting set problem

Let H=(V,E)H=(V,E) be a hypergraph with vertex set V   and edge set EE, where n:=|V|n:=|V| and m:=|E|m:=|E|. Let l   be the maximum size of an edge and Δ be the maximum vertex degree. A hitting set (or vertex cover) in HH is a subset of V in which all edges are incident. The hitting set problem is to find a hitting set of minimum cardinality. It is known that an approximation ratio of l can be achieved easily. On the other hand, for constant l, an approximation ratio better than l cannot be achieved in polynomial time under the unique games conjecture (Khot and Regev, 2008 [17]). Thus breaking the l-barrier for significant classes of hypergraphs is a complexity-theoretically and algorithmically interesting problem, which has been studied by several authors (Krivelevich, 1997 [18], Halperin, 2000 [12], Okun, 2005 [23]). We propose a randomised algorithm of hybrid type for the hitting set problem, which combines LP-based randomised rounding, graphs sparsening and greedy repairing and analyse it for different classes of hypergraphs. For hypergraphs with Δ=O(n14) and l=O(n) we achieve an approximation ratio of l(1−cΔ), for some constant c>0c>0, with constant probability. For the case of hypergraphs where l   and Δ are constants, we prove a ratio of l(1−l−18Δ). The latter is done by analysing the expected size of the hitting set and using concentration inequalities. Moreover, for quasi-regularisable hypergraphs, we achieve an approximation ratio of l(1−n8m). We show how and when our results improve over the results of Krivelevich, Halperin and Okun.