2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Clive Newstead Oct 18 '19 at 12:45
  • 1
    $\begingroup$ If $\Sigma$ is s set of subsets, then I'd rather expect $s_i\subseteq S$ instead of $s_i\in S$ $\endgroup$ – Hagen von Eitzen Oct 18 '19 at 13:10
  • $\begingroup$ The task is trivially unsolvable if any of the $s_i$ is empty or a singleton. $\endgroup$ – Hagen von Eitzen Oct 18 '19 at 13:11
  • $\begingroup$ 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. $\endgroup$ – Milo Brandt Oct 19 '19 at 14:48
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Konstantin Oct 18 '19 at 13:19
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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