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 k3 , this problem is known to be NP-hard. For general k , the problem was studied by Lov\'{a}sz (1975), who gave a 2k-approximation based on the standard LP relaxation. Subsequent work by Aharoni, Holzman, and Krivelevich (1996) showed a tight integrality gap of 2k−o(1) 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 0">0 is an arbitrarily small constant):

o NP-hardness of obtaining an approximation factor of 4k− for even k , and 4k−14k− for odd k ,

o NP-hardness of obtaining a nearly-optimal approximation factor of 2k−1+12k− , and,

o An optimal Unique Games-hardness for approximation within factor 2k− , 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− 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.