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-094 | 3rd December 2001 00:00

Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2 - \epsilon

RSS-Feed




TR01-094
Authors: Jonas Holmerin
Publication: 3rd December 2001 15:08
Downloads: 911
Keywords: 


Abstract:


We prove that Minimum vertex cover on 4-regular hyper-graphs (or
in other words, hitting set where all sets have size exactly 4),
is hard to approximate within 2 - \epsilon.
We also prove that the maximization version, in which we
are allowed to pick B = pn elements in an n-vertex hyper-graph,
and are asked to cover as many edges as possible,
is hard to approximate
within 1/(1 - (1-p)^4) - \epsilon when p \geq 1/2 and
within ((1-p)^4 + p^4)/(1 - (1-p)^4) - \epsilon when
p < 1/2. From this follows that the general problem when B is part of
the input is hard to approximate within 16/15 - \epsilon.
These results also hold for k-regular hyper-graphs when k > 4.



ISSN 1433-8092 | Imprint