An approximation algorithm for the partial vertex cover problem in hypergraphs

Let \(\mathcal {H}=(V,\mathcal {E})\) be a hypergraph with set of vertices \(V, n:=|V|\) and set of (hyper-)edges \(\mathcal {E}, m:=|\mathcal {E}|\). Let \(l\) be the maximum size of an edge, \(\varDelta \) be the maximum vertex degree and \(D\) be the maximum edge degree. 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. For the case of \(k=m\) and constant \(l\) it known that an approximation ratio better than \(l\) cannot be achieved in polynomial time under the unique games conjecture (UGC) (Khot and Ragev J Comput Syst Sci, 74(3):335–349, 2008), but an \(l\)-approximation ratio can be proved for arbitrary \(k\) (Gandhi et al. J Algorithms, 53(1):55–84, 2004). The open problem in this context has been to give an \(\alpha l\)-ratio approximation with \(\alpha < 1\), as small as possible, for interesting classes of hypergraphs. In this paper we present a randomized polynomial-time approximation algorithm which not only achieves this goal, but whose analysis exhibits approximation phenomena for hypergraphs with \(l\ge 3\) not visible in graphs: if \(\varDelta \) and \(l\) are constant, and \(2\le l\le 4\varDelta \), we prove for \(l\)-uniform hypergraphs a ratio of \(l\left( 1-\frac{l-1}{4\varDelta }\right) \), which tends to the optimal ratio 1 as \(l\ge 3\) tends to \(4\varDelta \). For the larger class of hypergraphs where \(l, l \ge 3\), is not constant, but \(D\) is a constant, we show a ratio of \(l(1-1/6D)\). Finally for hypergraphs with non-constant \(l\), but constant \(\varDelta \), we get a ratio of \( l (1- \frac{2 - \sqrt{3}}{6\varDelta })\) for \(k\ge m/4\), leaving open the problem of finding such an approximation for \(k < m/4\).