__
TR01-094 | 3rd December 2001 00:00
__

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

**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.