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?



3-Approximation Algorithm for 3-Hitting Set
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](https://en.wikipedia.org/wiki/Unique_games_conjecture), no polynomial-time algorithm can achieve a better approximation ratio. 


