Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-102 | 18th December 2001 00:00

Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.

RSS-Feed




TR01-102
Authors: Oded Goldreich
Publication: 18th December 2001 14:18
Downloads: 2142
Keywords: 


Abstract:

Using known results regarding PCP,
we present simple proofs of the inapproximability
of vertex cover for hypergraphs.
Specifically, we show that

(1) Approximating the size of the minimum vertex cover
in $O(1)$-regular hypergraphs to within a factor of~1.99999 is NP-hard.
(2) Approximating the size of the minimum vertex cover
in $4$-regular hypergraphs to within a factor of~1.49999 is NP-hard.

Both results are inferior to known results (by Trevisan and Holmerin),
but they are derived using much simpler proofs.
Furthermore, these proofs demonstrate the applicability
of the FGLSS-reduction in the context of reductions among
combinatorial optimization problems.



ISSN 1433-8092 | Imprint