I'm curious whether the problem below is NP-complete. I provide two simple definitions and one example at first.

Definition 1. Let $\langle {\cal{S}}_i\rangle\substack{i\in I}$ and $\langle {\cal{S}}_j\rangle\substack{j\in J}$ be two set families. A "cartesian union" of $\langle {\cal{S}}_i\rangle\substack{i\in I}$ and $\langle {\cal{S}}_j\rangle\substack{j\in J}$ is the family of sets $\langle {{\cal{S}}_i}\cup {{\cal{S}}}_j \mid i\in I, j\in J\rangle$. Denote the operation of cartesian union by $\biguplus$.

Definition 2. A set family ${\cal{S}}$ is said to be "decomposable into cartesian union" if ${\cal{S}}=A\biguplus B$, where $A$ and $B$ are families of non-empty sets with $A\neq\varnothing\neq B$.

Example: the following are decompositions into cartesian union

$\langle \langle a,b,x,y\rangle, \langle a,b,y\rangle, \langle c,d,x,y\rangle, \langle c,d,y\rangle \rangle = \langle \langle a,b\rangle, \langle c,d\rangle \rangle \biguplus \langle \langle x,y\rangle, \langle y\rangle\rangle$

$\langle \langle a,b,x,y\rangle, \langle a,b,y\rangle, \langle c,d,x,y\rangle, \langle c,d,y\rangle \rangle = \langle \langle a,b,x\rangle, \langle a,b\rangle, \langle c,d,x\rangle, \langle c,d\rangle \rangle \biguplus \langle \langle y\rangle \rangle$

Problem CDU (Decomposition into cartesian union). Given a non-empty finite family $\langle C_k\rangle\substack{k=1\ldots l}$ of finite sets, decide whether it is decomposable into cartesian union of families $\langle {\cal{S}}_i\rangle\substack{i=1\ldots m}$ and $\langle {\cal{S}}_j\rangle\substack{j=1\ldots n}$ such that $(\cup\substack{i=1\ldots m} {\cal{S}}_i) \bigcap (\cup\substack{j=1\ldots n} {\cal{S}}_j) = \varnothing$.

The Example above shows decompositions of this kind and I intensionally omit here the question of uniqueness of such decompositions. Clearly, the numbers $m$ and $n$ above must be related with $l$ as $l=m\times n$.

The Problem CDU is clearly in NP and seems to be NP-complete, but I can't find a suitable NP-complete problem for reduction. By the way, I haven't seen any problems related to the notion of cartesian product, except the cartesian decomposition problem for graphs which is tractable (http://www.mp.feri.uni-mb.si/osebne/peterin/clanki/algoritem12.ps).

The only suitable NP-complete problem for reduction I found so far is: http://en.wikipedia.org/wiki/Set_splitting_problem known also as 2-coloring problem for hypergraphs.