Efficient Scheduling for Parallel Memory Hierarchies
Rishi Saket
Apr 28, 2010


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 k-uniform k-partite hypergraphs, when the k-partition is given as input. For this problem Lovasz gave a k/2 factor LP rounding based approximation, and a matching k/2 - o(1) integrality gap instance was constructed by Aharoni etal.

In this work we prove that it is NP-hard to approximate the minimum vertex cover in k-uniform k-partite hypergraphs to within a factor of k/16 - eps, which is the the first strong hardness result for this problem (here eps ≥ 0 is an arbitrary constant). Our proof is based on a reduction from minimum vertex cover in r-uniform hypergraphs for which NP-hardness of approximating within r - 1 - eps was shown by Dinur etal.

In addition, we also prove a Unique Games-hardness of approximation factor of k/2 - eps, showing the optimality of Lovasz's algorithm under the Unique Games conjecture. The Unique Games-hardness result is obtained by applying the recent results of Kumar etal, with a slight modification, to the LP integrality gap due to Aharoni etal. The modification is to ensure that the reduction preserves the desired structural properties of the hypergraph.

Joint work with Venkatesan Guruswami.