I am not sure if you are looking for an exact polynomial algorithm or not. If so, I have bad news. This problem is NP-hard, due to a reduction from the vertex cover problem. In the following, please find a brief sketch of the proof/reduction (I did not deal with decision problems, it is very straightforward reduction after you read the following).

Given an instance of the vertex cover problem $I=\langle G=(V, E) \rangle$ (and possibly a $k$ in the instance of the decision problem), you can construct an instance of your own problem $I'= \langle S \rangle$ (and possibly a $k$ in the instance of the decision problem) that verifies the answer to the vertex cover problem. Let $G'=(V, E')$ be the complement graph of $G$, where there is an edge between two vertices $v_i$ and $v_j$ in $G'$, if and only if there is no edge between $v_i$ and $v_j$ in $G$. Assign each vertex $v_i \in V$ a set $S_i$, initially set to empty. Start with a vertex $v_1$ and for every neighbor $v_i$ of $v_1$, add the label $v_1i$ to both sets $S_1$ and $S_i$. Then, do the same thing for vertices $v_2$, ..., $v_n$. You will end up with a set $S=\{ S_1, \cdots, S_n \}$. If you solve your proposed problem over $S$, this is identical to the vertex cover of $G$.

Good news? You can apply all approximation and heuristic algorithms presented for vertex cover problem to your problem easily.

I am not sure if you are looking for an exact polynomial algorithm or not. If so, I have bad news. This problem is NP-hard, due to a reduction from the vertex cover problem. In the following, please find a brief sketch of the proof/reduction (I did not deal with decision problems, it is very straightforward reduction after you read the following).

Given an instance of the vertex cover problem $I=\langle G=(V, E) \rangle$ (and a $k$ in the instance of the decision problem), you can construct an instance of your own problem $I'= \langle S \rangle$ (and a $k$ in the instance of the decision problem) that decides the answer to the vertex cover problem. Let $G'=(V, E')$ be the complement graph of $G$, where there is an edge between two vertices $v_i$ and $v_j$ in $G'$, if and only if there is no edge between $v_i$ and $v_j$ in $G$. Assign each vertex $v_i \in V$ a set $S_i$, initially set to empty. Start with a vertex $v_1$ and for every neighbor $v_i$ of $v_1$, add the label $v_1i$ to both sets $S_1$ and $S_i$. Then, do the same thing for vertices $v_2$, ..., $v_n$. You will end up with a set $S=\{ S_1, \cdots, S_n \}$. If you solve your proposed problem over $S$, this is identical to the vertex cover of $G$.

Good news? You can apply all approximation and heuristic algorithms presented for vertex cover problem to your problem easily.