17
$\begingroup$

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.)

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Might you be looking for the set cover problem? $\endgroup$
    – Juho
    Aug 21, 2012 at 18:09
  • $\begingroup$ @Juho Not quite. In my example, the set cover problem would be to find a set of flags such that the union of those flags contains all of the colors used on all flags. By contrast, I’m looking for something that will spit just out a list of colors, not a list of flags, and I don’t need the set $M$ to contain every possible color. I’ll poke around this area on Wikipedia though, I think you’ve got me on the right track. Thanks! $\endgroup$
    – bdesham
    Aug 21, 2012 at 18:28

4 Answers 4

Reset to default
14
$\begingroup$

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).

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks. Can you provide a reference for somewhere to read about actual implementations? I.e. how would I translate my problem to a set-cover problem, and then how would I solve that? $\endgroup$
    – bdesham
    Aug 21, 2012 at 22:05
  • 1
    $\begingroup$ bdesham, think of each element as the set of sets it belongs to. run set cover on the elements-as-sets input. also, read the wiki page linked here. $\endgroup$
    – Sasho Nikolov
    Aug 22, 2012 at 0:49
  • $\begingroup$ Are you interested in an approximate solution, or do you want to have the exact solution? $\endgroup$
    – A.Schulz
    Aug 22, 2012 at 6:59
  • $\begingroup$ I’d like an exact solution. The data sets I’m working with are small enough that I don’t think that should be a problem. $\endgroup$
    – bdesham
    Aug 22, 2012 at 15:49
  • 1
    $\begingroup$ @Keyser: You are right. However it is common practice to associate the decision problem with the corresponding optimization problem since they are for NP-complete problems closely related. $\endgroup$
    – A.Schulz
    Nov 7, 2012 at 9:44
2
$\begingroup$

An idea that could help: if the intersection of all the sets in $\mathbf S$ in not empty, then you can pick any element $s$ in the intersection and set $M = \{s\}$. If the intersection is empty, find an element (color) $c$ whose occurrence in sets is maximum and replace all the sets in which it occurs by the singleton $\{c\}$. Keep doing this until every element's occurrence count is equal to $1$ and then set $M$ to the union of the remaining sets. For example, if $\mathbf S$ is the power set of some set $A$ then $M = A$. I might be wrong however.

Improve this answer
$\endgroup$
2
$\begingroup$

Have a look at Ray Reiter's "A Theory of Diagnosis from First Principles" where he gives an algorithm for computing hitting sets, and this additional note "A correction...".

The algorithm is generally known as "hitting set tree" algorithm, it shouldn't be too hard to find an implementation. You mentioned you weren't too interested in runtime, but optimisations such as early branch termination etc. are quite critical to the implementation, and interesting as well :)

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Can you summarize the algorithm to make your answer more self-contained? Links can and will break. $\endgroup$
    – Juho
    Aug 23, 2012 at 16:34
0
$\begingroup$

Practically speaking, one of the better ways (certainly one of the easiest) to solve instances of Set Cover/Hitting Set is mixed integer programming. This involves communicating the integer programming formulation to the solver of your choice.

Improve this answer
$\endgroup$

Your Answer

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

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