Inapproximability of minimum vertex cover on k-uniform k-partite hypergraphs

Abstract

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 ≥ 3, this problem is known to be NP-hard. For general k, the problem was studied by Lovász, who gave a k/2-approximation based on the standard LP relaxation. Subsequent work by Aharoni, Holzman, and Krivelevich showed a tight integrality gap of (k/2 - 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 is an arbitrarily small constant): NP-hardness of obtaining an approximation factor of (k/4 - ε) for even k and (k/4 - 1/4k - ε) for odd k, NP-hardness of obtaining a nearly optimal approximation factor of (k/2 - 1 + 1/2k - ε), and an optimal unique games-hardness for approximation within factor (k/2 - ε), showing the optimality of Lovász'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. 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, with a slight modification, to the LP integrality gap due to Aharoni, Holzman, and Krivelevich. 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 multilayered PCP of Dinur, Guruswami, Khot, and Regev and uses a gadget based on biased long codes adapted from the LP integrality gap of Aharoni, Holzman, and Krivelevich. Our reduction requires the analysis of several long codes with different biases, for which we prove structural properties of the so-called crossintersecting collections of set families, variants of which have been studied in extremal set theory.