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

• Is there any restriction on the elements of $\Sigma$? If not, the answer is no (in general)—for example, if $|S| \ge 2$ and $\Sigma$ contains at least two singletons, no such partition of $S$ exists. – Clive Newstead Oct 18 '19 at 12:45
• If $\Sigma$ is s set of subsets, then I'd rather expect $s_i\subseteq S$ instead of $s_i\in S$ – Hagen von Eitzen Oct 18 '19 at 13:10
• The task is trivially unsolvable if any of the $s_i$ is empty or a singleton. – Hagen von Eitzen Oct 18 '19 at 13:11
• If your subsets happen to all be of size $2$, this is the same as $2$-coloring the graph defined by the edges $\Sigma$, which can be solved by a greedy algorithm. – Milo Brandt Oct 19 '19 at 14:48

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.

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

• Dear friends, I should give more exact statement of the problem. Given above mention conditions, is it possible to split the set $S$ in such a way? It's obvious, that in some cases the answer is No, in some -- Yes. The algorithm that return the answer is required. – Konstantin Oct 18 '19 at 13:19

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