2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – D.W. ♦
    Commented Mar 31, 2016 at 9:42

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Cromack
    Commented Mar 31, 2016 at 9:39
  • $\begingroup$ @Cromack 3-Hitting Set is NP-complete, so of course your problem (which is in NP) can be reduced to 3-Hitting Set. $\endgroup$
    – Tom van der Zanden
    Commented Mar 31, 2016 at 9:46
  • $\begingroup$ @KKS Yes, for proving NP-completeness of my problem, we give a reduction from 3-Hitting Set to it, but what if a wanted to reduce my problem to 3-Hitting Set in order to use an efficient approximation algorithm already known for 3-Hitting Set? In such a case, wouldn't those sets with cardinality 4 be problematic? $\endgroup$
    – Cromack
    Commented Apr 1, 2016 at 7:52
  • 1
    $\begingroup$ You could do as follows. Check those 4-sets that do not intersect with the others. Choose some element in each of them and throw them away. For each set from the rest take its intersection with some other. It will be at most 3-set. If not then two sets coincide and you can throw it out and intersect with some other until you get 3-set. $\endgroup$
    – KKS
    Commented Apr 1, 2016 at 8:45
  • 1
    $\begingroup$ @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" $\endgroup$
    – KKS
    Commented Apr 1, 2016 at 18:39

Your Answer

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

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