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 $k \ge 3$, this problem is known to be NP-hard. For general $k$, the problem was studied by Lov\'{a}sz (1975), who gave a $\frac{k}{2}$-approximation based on the standard LP relaxation. Subsequent work by Aharoni, Holzman, and Krivelevich (1996) showed a tight integrality gap of $\left(\frac{k}{2} - o(1)\right)$ for the LP relaxation.

We further investigate the inapproximability of minimum vertex cover on $k$-uniform $k$-partite hypergraphs and present the following results (here $\epsilon > 0$ is an arbitrarily small constant):

o NP-hardness of obtaining an approximation factor of $\left(\frac{k}{4} - \epsilon \right)$ for even $k$, and $\left(\frac{k}{4} - \frac{1}{4k} - \epsilon\right)$ for odd $k$,

o NP-hardness of obtaining a nearly-optimal approximation factor of $\left(\frac{k}{2}-1+\frac{1}{2k}-\epsilon\right)$, and,

o An optimal Unique Games-hardness for approximation within factor $\left(\frac{k}{2} - \epsilon\right)$, showing the optimality of Lovasz's algorithm if one assumes the Unique Games conjecture.

The first hardness result is based on a reduction from minimum vertex cover in $r$-uniform hypergraphs, for which NP-hardness of approximating within $r - 1 -\epsilon$ was shown by Dinur, Guruswami, Khot, and Regev (2005). We include it for its simplicity, despite it being subsumed by the second hardness result. The Unique Games-hardness result is obtained by applying the results of Kumar, Manokaran, Tulsiani, and Vishnoi (2011), with a slight modification, to the LP integrality gap due to Aharoni et al. The modification ensures that the reduction preserves the desired structural properties of the hypergraph.

The reduction for the nearly optimal NP-hardness result relies on the Multi-Layered PCP of [DGKR05], and uses a gadget based on biased Long Codes, which is adapted from the LP integrality gap for the problem. The nature of our reduction requires the analysis of several Long Codes with different biases, for which we prove structural properties of cross-intersecting collections of set families, variants of which have been studied in extremal set theory.