15
$\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.)

$\endgroup$
  • 2
    $\begingroup$ Might you be looking for the set cover problem? $\endgroup$ – Juho Aug 21 '12 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 '12 at 18:28
13
$\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).

$\endgroup$
  • $\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 '12 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 '12 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 '12 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 '12 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 '12 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.

$\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 :)

$\endgroup$
  • 2
    $\begingroup$ Can you summarize the algorithm to make your answer more self-contained? Links can and will break. $\endgroup$ – Juho Aug 23 '12 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.

$\endgroup$

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.