On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs

<p>Computing a minimum vertex cover in graphs and hypergraphs is a well-studied optimizaton problem. While intractable in general, it is well known that on bipartite graphs, vertex cover is polynomial time solvable. In this work, we study the natural extension of bipartite vertex cover to hypergraphs, namely finding a small vertex cover in <em>k</em>-uniform <em>k</em>-partite hypergraphs, when the <em>k</em>-partition is given as input. For this problem Lovász [16] gave a k2 factor LP rounding based approximation, and a matching (k2−o(1)) integrality gap instance was constructed by Aharoni <em>et al.</em> [1]. We prove the following results, which are the first strong hardness results for this problem (here <em>ε</em>> 0 is an arbitrary constant):</p> <ul> <li> <p>NP-hardness of approximating within a factor of (k4−ε), and</p> </li> <li> <p>Unique Games-hardness of approximating within a factor of (k2−ε), showing optimality of Lovász’s algorithm under the Unique Games conjecture.</p> </li> </ul> <p>The NP-hardness result is based on a reduction from minimum vertex cover in <em>r</em>-uniform hypergraphs for which NP-hardness of approximating within <em>r</em>–1–<em>ε</em> was shown by Dinur <em>et al.</em>[5]. The Unique Games-hardness result is obtained by applying the recent results of Kumar <em>et al</em>. [15], with a slight modification, to the LP integrality gap due to Aharoni <em>et al</em>. [1]. The modification is to ensure that the reduction preserves the desired structural properties of the hypergraph.</p>