A natural problem on "cartesian union" of set families (hypergraphs). Are there NP-complete problems related to the notion of cartesian product?

Question

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$, for some families $A$ and $B$ 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\ell}$ 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 $(\bigcup\substack{i=1\ldots m} \cal S_i) \cap (\bigcup\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 $\ell$ as $\ell=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.

Answer 1

As a combinatorial problem, CDU was considered in detail (for clutters) by Billera, who attributes its solution to Shapley.

Louis J. Billera, On the Composition and Decomposition of Clutters. J. Combinatorial Theory 11, 234-245 (1971).

Interestingly, I happened upon this old post by searching for formulas containing the disjoint union operator.

http://searchonmath.com/result?equation=%5Cbiguplus

Answer 2

I would propose to investigate a solution established in

1. Emelyanov P. On Two Kinds of Dataset Decomposition // Proceedings of the 18th International Conference on Computational Science (ICCS 2018). Part II, 11-13 Juin 2018, Wuxi, China / Lecture Note in Computer Science. – Vol. 10861, – Springer, 2018. – P. 171-183. DOI: 10.1007/978-3-319-93701-4_13.

2. Emelyanov P. and Ponomaryov D. The Complexity of AND-decomposition of Boolean Functions // Discrete Applied Mathematics. 280 (2020). pp. 113–132. DOI: 10.1016/j.dam.2019.07.005.