Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.