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

Question

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.

Answer 1

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 1: Maximal matching Pick a maximal matching, and take all vertices containing it. This is a vertex cover since if there is an edge which isn't covered, the matching isn't maximal. Every vertex cover must contain at least one vertex per edge in the matching, and our solution contains two vertices per matching edge, hence it's a 2-approximation.

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.