MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 (

The only suitable NP-complete problem for reduction I found so far is: known also as 2-coloring problem for hypergraphs.

share|cite|improve this question
You need to make clear whether you mean family or sequence. If the latter (and you are using finite sequences), then it should be equivalent to factoring. If the former, then the operator is idempotent on union closed families A and there are plenty of examples where l = mxn fails. (Of course, the condition is needed for a disjoint decomposition.) Gerhard "Ask Me About Frankl's Problem" Paseman, 2012.09.22 – Gerhard Paseman Sep 22 '12 at 12:24
In the above mentioned, I mean families of sets. Of course, the equality l = m x n was noted in the context of disjoint decompositions. Definition 2 is auxiliary and admits non-intended (non-disjoint) decompositions like e.g. {A,B} = {A,B} \biguplus {{A},{B}} for which the equality does not hold. We are interested in disjoint decompositions, the Problem CDU. Could you explain your idea on the case with sequences instead of set families? – Martin Oct 1 '12 at 3:34

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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