TR02-027 Authors: Irit Dinur, Venkatesan Guruswami, Subhash Khot

Publication: 30th April 2002 03:55

Downloads: 1800

Keywords:

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 \geq 5$, E$k$-Vertex-Cover is

NP-hard to approximate within a factor of $(k-3-\epsilon)$, for

an arbitrarily small constant $\epsilon > 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-\epsilon}$.

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 $\Omega(k)$, followed by a stronger construction that

obtains the $(k-3-\epsilon)$ 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-\epsilon)$ assuming the

hardness of $O(\log n)$-coloring a $c$-colorable graph for some fixed

$c \ge 3$.