# Better approximation for special case of 3-hitting set

I have a question based on 3-Hitting Set problem. In this problem, we are given a universal set U of size n and a set of subsets S such that $\forall$ s $\in$ S |s|<=3. FOr this problem, Integer programming formulation is given by $x_{a}+x_{b}+x_{c} >=1$ (a,b,c) $\in$ S

$\forall x_{i} \in$(1,0) where $i=1,2 \ldots n$

minimize $\sum x_{i}$

where each variable $x_i$ corresponds to element $i\in$ U.

A Linear programming relaxation would be 0<=$x_{i}$=<1 instead of $x_{i} \in$ {1,0}

After performing linear programming we know that In Every s $\in$S x_{a}+x_{b}+x_{c} >=1 at least one of $x_{i}>=\frac{1}{3}$ so $x_{i}>=\frac{1}{3}$ is made as 1 and the corresponding elements are selected in the solution. There may exist a set s such that $x_{a}+x_{b}+x_{c} >=1$ so that $x_{a},x_{b},x_{c}>=\frac{1}{3}$ and we will be picking all three elements. This way, we will get a three approximation after rounding $x_{a},x_{b},x_{c}$ to 1.

My question is

I look at a special case of 3 -hitting set H' in which size of each set s is exactly 3 and optimal solution for linear programming problem is $\forall x_i =\frac{1}{3}$. Now, is it possible to improve the approximation factor to less than 3

• You may want to consider what LP duality tells you: I think it gives that you can assign rational nonnegative weights to edges such that the weighted degree of each vertex is 1. This sounds related to whether the problem is easier on "regular" instances where every vertex appears in the same number of sets. – daveagp Oct 8 '10 at 10:55

What you've defined is the vertex cover problem for 3-uniform hypergraphs. Khot and Regev showed that if the unique games conjecture is true, then it is NP-hard to get an approximation of $3-\epsilon$ for this problem.
• it is Np-hard for general 3-hitting set problem but here there is additional information that linear programming gives a optimal solution as each $x_i=\frac{1}{3}$ for i=1,2 $\ldots$n. Is this information will not help us in better approximation. – Prabu Oct 9 '10 at 5:24
• Since vertex cover related to this problem .Let me state the problem in terms of vertex cover .Given a Graph G(V,E) ,Integer programming formulation for vertex cover is $x_{i} + x_{j}>=1$ where (i,j) $\in$ E through LP-relaxation we get a 2- approximation. Now i give a special graph G' with the property that optimal solution for linear programming is $x_{i}= \frac{1}{2}$. Is this approximation can not improved over 2 for these special graph G' – Prabu Oct 9 '10 at 6:37