# Is this a well-known NP-hard problem?

Let $R = \{1, \ldots, n\}$ and $S = \{S_1, \ldots, S_m\}$ a collection of subsets of $R$ such that $R = \bigcup_{i = 1}^m S_i$ and, for $n > 3$, $$3 \leq \vert S_i \vert \leq 4 \, , \enspace i \in \{1, \ldots, m\} \, .$$

Then, I want to know the subset—or subsets, since there may be more than one valid solution—$T$ with minimum cardinality such that every $S_i$ has at least one element in $T$. I suspect this is an NP-hard problem (or NP-complete in its decision version), but I don't know if it's one that has a name.

As an example, consider $R = \{1, 2, 3, 4, 5\}$ and $S = \{S_1, \ldots, S_9\}$, where

• $S_1 = \{1, 2, 3\} \, , \enspace S_4 = \{1, 4, 5\} \, , \enspace S_7 = \{1, 2, 3, 4\} \, ,$
• $S_2 = \{1, 2, 4\} \, , \enspace S_5 = \{2, 3, 5\} \, , \enspace S_8 = \{1, 3, 4, 5\} \, ,$
• $S_3 = \{1, 2, 5\} \, , \enspace S_6 = \{3, 4, 5\} \, , \enspace S_9 = \{2, 3, 4, 5\} \, .$

Here, the solutions are $T = \{\{1, 3\}, \{1, 5\}, \{2, 4\}, \{2, 5\}\}$. (I'd be happy even if I knew just one of them.)

Note that I'm not asking for an algorithm to solve the problem. I just want to know where this is or reduces to a well-known problem.

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. In particular, it would help to make it more focused on your problem (there are many problems where we could ask whether they are NP-hard). Thank you! – D.W. Mar 31 '16 at 9:42

3-Hitting Set problem is known in parameterized complexity theory. The requirement $\cup S_i=R$ can always be assumed without loss of generality. See e.g. An efficient fixed-parameter algorithm for 3-Hitting Set. According to this link it is NP-hard in its usual (not parameterized) form. Proving NP-completeness of your problem we give reduction FROM 3-Hitting Set to your problem not vica versa. Therefore your problem is NP-complete (in its decision form).
• Thank you very much for your answer. I have a doubt though: since the cardinality of some $S_i$ may be $4$, does it allow us to reduce this problem to the 3-Hitting Set problem? – Cromack Mar 31 '16 at 9:39
• @Cromack Moreover it could be assumed without loss of generality that each element of Hitting Set belongs to maximum (with respect to inclusion) feasible (i.e. having nonempty intersection) subsystem of sets $S_i.$ Then some set $S_i$ could be removed if it is contained in all MFSs to which the other $S_j$ belongs. See the paper "link.springer.com/article/10.1134%2FS0005117912020130#page-1" – KKS Apr 1 '16 at 18:39