5
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How do I extend it for $k>2$, what is an edge that connects 3 vertices? $\endgroup$ – SIMEL Nov 14 '16 at 21:40
  • 4
    $\begingroup$ @IlyaMelamed That's the point where you get to say that you did your homework rather than getting somebody on the internet to do it for you. $\endgroup$ – David Richerby Nov 14 '16 at 21:43
  • $\begingroup$ @IlyaMelamed An edge connecting more than two vertices is a hyperedge. $\endgroup$ – David Richerby Nov 14 '16 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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