Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε
Jonas Holmerin · 2002
(MATH) We prove that Minimu Vertex Cover on 4-regular hyper-graphs (or in other words, Minimum Hitting Set where all sets have size exactly 4), is hard to approximate within $2 - ε. 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) - ε when p ≤ 1/2 and within ((1—p)4 + p4)/(1 — (1—p)4) — ε 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 - ε.