2011/05/20 by Sushant Sachdeva, Sachdeva, Sushant, Rishi Saket +1
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Complexity and Algorithms in Graphs #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1105.4175
We study the problem of computing the minimum vertex cover on k-uniform\nk-partite hypergraphs when the k-partition is given. On bipartite graphs (k =\n2), the minimum vertex cover can be computed in polynomial time. For general k,\nthe problem was studied by Lov 'asz, who gave a k/2 -approximation based on the\nstandard LP relaxation. Subsequent work by Aharoni, Holzman and Krivelevich\nshowed a tight integrality gap of (k/2 - o(1)) for the LP relaxation. While\nthis problem was known to be NP-hard for k >= 3, the first non-trivial\nNP-hardness of approximation factor of k/4- eps was shown in a recent work by\nGuruswami and Saket. They also showed that assuming Khot's Unique Games\nConjecture yields a k/2 - eps inapproximability for this problem, implying the\noptimality of Lov 'asz's result.\n In this work, we show that this problem is NP-hard to approximate within k/2-\n1 + 1/2k - eps. This hardness factor is off from the optimal by an additive\nconstant of at most 1 for k >= 4. Our reduction relies on the Multi-Layered PCP\nof Dinur et al. and uses a gadget - based on biased Long Codes - adapted from\nthe LP integrality gap of Aharoni et al. The nature of our reduction requires\nthe analysis of several Long Codes with different biases, for which we prove\nstructural properties of the so called cross-intersecting collections of set\nfamilies - variants of which have been studied in extremal set theory.\n