3-Approximation Algorithm for 3-Hitting Set

Question

I need to find a $3$-approximation algorithm for finding a $3$-hitting set.

The set-up is that I have a set $S$ and a family $\mathcal{F}$ of subsets of $S$, where each member of $\mathcal{F}$ contains exactly $3$ elements. I need to find a hitting set (a set which intersects all members of $\mathcal{F}$) with the minimum number of elements.

If instead all the sets have size $2$, I already know that I can use the vertex cover problem to find a $2$-hitting set. For example, we can make a graph $G(V,E)$ where $V=S$ and $E=\mathcal{F}$. Then a vertex cover is also a hitting set.

But how would this work if the subsets of $S$ must have $3$ elements? And can we get a $3$-approximation algorithm?

I just learned about hypergraphs and I have a feeling that goes in the right way?

Answer 1

Let $\mathcal{H}$ be a hypergraph where each hyperedge has size $3$. A vertex cover is a set of vertices $X$ such that every hyperedge is incident to a vertex in $X$. Rephrased, our goal is to find a small vertex cover. One way to do this is to solve a dual problem. A matching in $\mathcal{H}$ is a set $M$ of hyperedges such that no two members of $M$ share a vertex. Now, find a maximal matching $M$ in $\mathcal{H}$. This can be done greedily. Letting $X$ be the vertices covered by $M$, we have that $X$ is a vertex cover. Moreover, the size of $X$ is at most $3$ times the size of a minimum vertex cover, because every vertex cover must use a vertex from each hyperedge in $M$. So, this is a polynomial-time $3$-approximation algorithm. Moreover, assuming the Unique Games Conjecture, no polynomial-time algorithm can achieve a better approximation ratio.