Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs

We study the problem of computing the minimum vertex cover on

k

-uniform

k

-partite hypergraphs when the

k

-partition is given. On bipartite graphs (

k

 = 2), the minimum vertex cover can be computed in polynomial time. For general

k

, the problem was studied by Lovász [23], who gave a

$\frac{k}{2}$

-approximation based on the standard LP relaxation. Subsequent work by Aharoni, Holzman and Krivelevich [1] showed a tight integrality gap of

$\left(\frac{k}{2} - o(1)\right)$

for the LP relaxation. While this problem was known to be NP-hard for

k

 ≥ 3, the first non-trivial NP-hardness of approximation factor of

$\frac{k}{4}-\varepsilon $

was shown in a recent work by Guruswami and Saket [13]. They also showed that assuming Khot’s Unique Games Conjecture yields a

$\frac{k}{2}-\varepsilon $

inapproximability for this problem, implying the optimality of Lovász’s result.

In this work, we show that this problem is NP-hard to approximate within

$\frac{k}{2}-1+\frac{1}{2k}-\varepsilon $

. This hardness factor is off from the optimal by an additive constant of at most 1 for

k

 ≥ 4. Our reduction relies on the

Multi-Layered PCP

of [8] and uses a gadget – based on biased Long Codes – adapted from the LP integrality gap of [1]. The nature of our reduction requires the analysis of several Long Codes with different biases, for which we prove structural properties of the so called

cross-intersecting

collections of set families – variants of which have been studied in extremal set theory.