2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.