ECCC-Report TR02-027https://eccc.weizmann.ac.il/report/2002/027Comments and Revisions published for TR02-027en-usTue, 30 Apr 2002 03:55:49 +0300
Paper TR02-027
| Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-\epsilon) |
Irit Dinur,
Venkatesan Guruswami,
Subhash Khot
https://eccc.weizmann.ac.il/report/2002/027Given 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$.
Tue, 30 Apr 2002 03:55:49 +0300https://eccc.weizmann.ac.il/report/2002/027