Given a set of sets, find the smallest set(s) containing at least one element from each set

Problem Detail: 

Given a set $\mathbf{S}$ of sets, I'd like to find a set $M$ such that every set $S$ in $\mathbf{S}$ contains at least one element of $M$. I'd also like $M$ to contain as few elements as possible while still meeting this criterion, although there may exist more than one smallest $M$ with this property (the solution is not necessarily unique).

As a concrete example, suppose that the set $\mathbf{S}$ is the set of national flags, and for each flag $S$ in $\mathbf{S}$, the elements are the colors used in that nation's flag. The United States would have $S = \{red, white, blue\}$ and Morocco would have $S = \{red, green\}$. Then $M$ would be a set of colors with the property that every national flag uses at least one of the colors in $M$. (The Olympic colors blue, black, red, green, yellow, and white are an example of such an $M$, or at least were in 1920.)

Is there a general name for this problem? Is there an accepted "best" algorithm for finding the set $M$? (I'm more interested in the solution itself than in optimizing the process for computational complexity.)

Asked By : bdesham

Answered By : A.Schulz

The problem is the well-known NP-complete problem Hitting Set. It is closely related to Set-Cover. The NP-completeness proof can found in the classic book of Garey and Johnson.

If you want to approximate it, you might want to translate your instance first to Set-Cover, and then apply an approximation algorithm for Set-Cover. However, Set-Cover cannot be be approximated by a constant factor in polynomial time, unless P=NP as shown by Lund and Yannakakis.

If you are interested in exact solutions and your inputs behave nicely, I would recommend using a fixed-parameter tractable. The running time is here not only expressed in terms of the input length $n$ but also in terms of an additional parameter $k$. If the running time is $O(f(k)\cdot n^{O(1)})$, we call the algorithm a FPT-algorithm. Here, $f(k)$ is an increasing function. So if $k$ is constant we have a polytime algorithm. The first chapter of the book by Flum and Grohe, explains an FPT-algorithm for hitting set (more precisely for $p$-card-hitting set). The algorithm is easy to implement and uses the method of bounded search trees. Still it needs to much space to explain here, basically you break down the necessary(?) brute-force search, into small pieces (when $k$ is small).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3276