# Find an algorithm that finds a minimal hitting set for sets limited in size

Given a family of sets $F=\{S_1,...,S_m\}$, where $S_i{\subseteq}\{1..n\}$, with the assumption that the maximum size of any set $S_i$ is at most $k$ ($|S_i|{\leq}k\ {\forall}i\in\{i..n\}$).

I'm tasked with finding a hitting set $H$, a set that contains at least one member from each set $S_i$ ($H{\cap}S_i\ne\emptyset\ {\forall}i\in\{1..n\}$). And to prove that the algorithm gives produces a set that is at most k times larger than the minimal hitting set.

What algorithm does it and how do I prove that it does it.

I've tried the greedy algorithm (take the number that covers the most sets, remove those sets, repeat).

I've also tried making the problem into a two sided graph where one side is the numbers, the other side are the sets and edges connect sets with their members, and applying a minimum cover set algorithm.

For both instances I couldn't show that the hitting set it gives is at most a set k times larger than the minimum.

Here are two algorithms for the case $k=2$, also known as Vertex Cover; we think of the sets $S_i$ as edges and of the elements $\{1,\ldots,n\}$ as vertices. We can assume that each edge connects two vertices, since singleton edges can easily be eliminated.
Both algorithms below can be extended to the case of general $k$.
Algorithm 2: Linear programming Consider the following LP relaxation: there is a variable $0 \leq x_i \leq 1$ for every vertex, and a constraint $x_i + x_j \geq 1$ for every edge $(i,j)$. Find a solution minimizing $\sum_i x_i$, and take all vertices such that $x_i \geq 1/2$. This is clearly a vertex cover, and its value is at most twice the value of the LP, hence it's a 2-approximation.
• How do I extend it for $k>2$, what is an edge that connects 3 vertices? Nov 14, 2016 at 21:40