期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2002
卷号：2002
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Given a k -uniform hypergraph, the E k -Vertex-Cover problem is to find a minimum subset of vertices that ``hits'' every edge. We show that for every integer k 5 , E k -Vertex-Cover is NP-hard to approximate within a factor of ( k − 3 − ) , for an arbitrarily small constant 0"> 0 . This almost matches the upper bound of k for this problem, which is attained by the straightforward greedy approximation algorithm. The best previously known hardness result was due to Holmerin, who showed the NP-hardness of approximating E k -Vertex-Cover within a factor of k 1 − . We present two constructions: one with a simple, purely combinatorial analysis, showing E k -Vertex-Cover to be NP-hard to approximate to within a factor ( k ) , followed by a stronger construction that obtains the ( k − 3 − ) inapproximability bound. The latter construction introduces a novel way of combining ideas from Dinur and Safra's paper, and the notion of covering complexity introduced by Guruswami, Hastad and Sudan. This also allows us to prove a hardness factor of ( k − 1 − ) assuming the hardness of O ( log n ) -coloring a c -colorable graph for some fixed c 3 .
关键词：hardness of approximation , Hitting Set , PCP , Vertex Cover
5 , E k -Vertex-Cover is NP-hard to approximate within a factor of ( k − 3 − 
