ECCC-Report TR01-094https://eccc.weizmann.ac.il/report/2001/094Comments and Revisions published for TR01-094en-usMon, 03 Dec 2001 15:08:40 +0200
Paper TR01-094
| Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2 - \epsilon |
Jonas Holmerin
https://eccc.weizmann.ac.il/report/2001/094
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.
Mon, 03 Dec 2001 15:08:40 +0200https://eccc.weizmann.ac.il/report/2001/094