How to split a set into two disjoint subsets in a special way? Suppose $S$ is a finite set (the number of its members is not large).
The set $\Sigma=\{s_1, \ldots, s_N\}$ is a set of subsets of $S$, i. e. $s_i \in S$. 
Is it possible to split $S$ into disjoint parts $S_1$ and $S_2$ that for any $i$: $s_i \cap S_1 \not= \emptyset$ and $s_i \cap S_2 \not= \emptyset$ (in other words, any $s_i$ is composed from both $S_1$ and $S_2$)?
I seek an algorithm enabling to decide if such division is possible (or not).
 A: This is called the set splitting problem.
You can use integer linear programming. For each $j\in S$, let binary decision variable $x_j$ indicate whether element $j$ is in $S_1$.  The constraints are $1\le \sum_{j\in s_i} x_j \le |s_i|-1$ for all $i$.  If the problem is feasible, the values of $x$ determine such a bipartition. If the problem is infeasible, then no such bipartition exists.
A: Not in general, to give an example: Let $S=\{1,2,3\}$ and let $s_{1}=\{1,2\},\ s_{2}=\{1,3\}$ and $s_{3}=\{2,3\}$. 
Then any non-empty disjoint pair $S_{1},S_{2}\subset S$ such that $S_{1}\cup S_{2}=S$ does not satisfy $s_{i}\cap S_{1}\neq\emptyset$ and $s_{i}\cap S_{2}\neq\emptyset$ for all $i$.
A: @FlorisClaassens example shows, I think $\Sigma$ is also a partition of $S$, not an arbitrary set of subsets of $S$!
In that case as @CliveNewstead said, you must to have no singleton.
Now if two above condition hold, the answer is actually Yes. In fact you can split any $s_i$ to two partition $s_i \cap S_1 \ \& \ s_i \cap S_2$. It likes an algorithm for smalling partitions.
