Given N sets of disjoint subsets, find a set of disjoint subsets such that it satisfies a criteria

Question

Given a collection of sets $S_i$ of disjoint subsets $sub_i$ of a set $X$, find a set $A$ of disjoint subsets $asub$ such that each one of these subsets is subset or equal to at most one subset in each of $S_i$, i.e., for

$S_1$ = $\{sub_11,sub_12,sub_13\}$, where $sub_11$, $sub_12$, $sub_13$ are disjoint,

$S_2$ = $\{sub_21,sub_22\}$, where $sub_21$, $sub_22$ are disjoint

Then find $A$ = $\{asub1,asub2,asub3\}$, where $asub1$, $asub2$ are disjoint

and

$asub1$ can be a subset of only one of $sub_11$ or $sub_12$ or $sub_13$ but not more than one of them. Same goes for $asub2$ and $asub3$.

Similarly

$asub1$ can be a subset of only of either $sub_21$ or $sub_22$ or but not both of them. Same goes for $asub2$ and $asub3$.

More formally,

$\forall sub_i \in S_i,$ and given a subset $asub \in A,$

If $Asub=\{sub_i\mid asub\subseteq sub_i\}$

$then$ $|Asub|=1$

$Example 1:$

$X = \{e1,e2,e3,e4,e5\}$

$S_1 = \{\{e1,e2\},\{e3,e4\},\{e5\}\}$

$S_2 = \{\{e1\},\{e2,e3,e4\},\{e5\}\}$

$S_3 = \{\{e1,e2,e3,e4\},\{e5\}\}$

$A= \{\{e1\},\{e2\},\{e3,e4\},\{e5\}\}$

$Example 2:$

$X = \{e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12\}$ $S_1 = \{\{e1,e2,e11,e12\},\{e3,e4,e5,e6\},\{e7,e8,e9,e10\}\}$ $S_2 = \{\{e1,e2,e3\},\{e4,e5,e6,e7,e8\},\{e9,e10,e11\},\{e12\}\}$

$A= \{\{e1,e2\},\{e3\},\{e4,e5,e6\},\{e7,e8\},\{e9,e10\},\{e11\},\{e12\}\}$

Preferably the algorithm for finding $A$ should take optimal time.

P.S. Forgive me if the mathematical description of the problem is not formal enough or if there are mistakes in it, I am not a mathematician.

Answer 1

Without loss of generality, each asub$i$ can be taken to have exactly one element (size 1). (If there is any solution, then there is a solution where all asub$i$'s are of size 1.)

Now it's easy to iterate over all sets of size 1 and determine which are valid for asub$i$. Let $A$ be the collection of all such sets. There is your solution. As a bonus, I even gave you a solution where $A$ is as large as possible.

The running time is polynomial (in fact, quadratic), so this should be an efficient algorithm.