3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Sep 22, 2012 at 12:24
  • $\begingroup$ 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? $\endgroup$
    – Martin
    Oct 1, 2012 at 3:34

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I don't understand. Are you saying that these papers (are they yours?) answer the question? If so, then what is the answer? $\endgroup$
    – LSpice
    Apr 30, 2023 at 0:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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