3
$\begingroup$

Define a universe U containing N elements. We are given N sets, each of which is a set.

For example, U = {1, 2, 3, 4} and sets

S1 = {{1}, {2, 4}}, 
S2 = {{2}, {1, 3}}, 
S3 = {{3}, {2, 4}},
S4 = {{4}, {1, 3}}

The goal is to find the smallest subset of U that contains at least one element from each of the N sets. So for example, the subset {1,3} is a correct answer while the subset {1,2} is not because it does not contain any set in S3, S4.

I tried to formulate the above as an instance of the hitting set problem (because it seemed closer to it in spirit), but failed to do so. One way I managed to cleanly reduce the problem is by expanding each set to include all supersets. Then the desired answer is the smallest sized set in the intersection of the expanded sets. But this approach is undesirable as the expanded set size grows exponentially.

Any thoughts on connections to a known complexity problem are much appreciated.

$\endgroup$
3

1 Answer 1

2
$\begingroup$

Thinking of the hitting set problem is the right idea. This problem (let's call it CONTAINMENT) is NP complete. It is clearly in NP, and

Theorem: $\text{CONTAINMENT}$ is NP-hard.

Proof: We reduce the minimal vertex cover problem$^1$ (known to be NP-hard) to an instance of $\text{CONTAINMENT}$. Given a graph $G$ with vertices $V$ (WLOG assume they are numbered from $1$ to $|V|$) and edges $E$, for each edge $e_i = (u,v) \in E$, we create the set $S_i = \{\{u\}, \{v\}\}$. Since you seem to require that the number of sets $S_i$ is the same as the number of elements in $U$, we can do the following. Set $U = \{1, 2, \cdots, \max(|V|, |E|)\}$. If $n = |E|$, then last $|E| - |V|$ elements will never appear in a set that is an element of any $S_i$ (they are in essence irrelevant to the reduction and are only present to satisfy the demands for the input of your problem). If $n = |V|$, then in addition to the $S_i$ we created above (there are $|E|$ such sets) we can add $|V| - |E|$ extra sets $S_i$ where $S_i = \{ \emptyset \}$ (the set where its only element is the empty set). (The condition for these $S_i$ will be trivially satisfied.) Note that the output of this reduction has size $O(\max(|E|, |V|))$.

Running $\text{CONTAINMENT}$ on this reduction will return a set of vertices corresponding to minimal vertex cover of $G$. A minimal vertex cover must cover at least one of the singleton sets in each of the $S_i$, which is exactly what your problem demands. $\square$

Footnotes:

  1. The minimum vertex cover problem asks of a graph $G = (V, E)$ to find $U \subseteq V$, with $|U|$ as minimal as possible, such that every edge in $E$ is incident to a vertex in $U$.
$\endgroup$
3
  • $\begingroup$ Thanks for the detailed answer. A related followup question: is it possible to obtain a connection in the opposite direction? Such a connection would help in using existing approximation algorithms (and other results) to solve this problem in practice. The intuition above is to model edges in the vertex cover as sets of single elements. Unfortunately, the reverse doesn't work, so I'm currently stuck at figuring out how to model sets of more than one elements. $\endgroup$
    – da4kc0m3dy
    Commented Nov 2, 2020 at 16:44
  • $\begingroup$ @da4kc0m3dy I'd have to think about it. For your question, is there any restriction on how many elements each $S_i$ can contain? $\endgroup$
    – paulinho
    Commented Nov 2, 2020 at 17:14
  • $\begingroup$ The broadest version of this problem does not have any restriction. But if it helps, please feel free to try to work on a constrained version of the problem that limits the size of subsets. So if only 2-sized subsets are allowed in each $S_i$, the size of $S_i$ would be less than $N^2 + N$ ($N$ for the one-sized sets). $\endgroup$
    – da4kc0m3dy
    Commented Nov 2, 2020 at 17:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .